Description

There are $n$ cities and $m$ directed roads, with cities numbered from $1$ to $n$. Each road connects two different cities, and for any two roads, either their starting cities differ or their ending cities differ. Therefore, $n$ and $m$ satisfy $m \le n(n-1)$.

Given two cities $a$ and $b$, you can sort all simple paths (each city appears at most once, including the start and end) from $a$ to $b$: first by total length in ascending order, and if lengths are equal, by lexicographical order in ascending order. Your task is to find the $k$-th shortest path from $a$ to $b$.

Input Format

The first line contains five positive integers $n, m, k, a, b$.

Each of the following $m$ lines contains three integers $u, v, l$, indicating there is a directed road from city $u$ to city $v$ with length $l$.

Output Format

If there are fewer than $k$ simple paths from $a$ to $b$, output No. Otherwise, output the $k$-th shortest path: starting from city $a$, output each visited city in order until city $b$, separated by hyphens -.

5 20 10 1 5
1 2 1
1 3 2
1 4 1
1 5 3
2 1 1
2 3 1
2 4 2
2 5 2
3 1 1
3 2 2
3 4 1
3 5 1
4 1 1
4 2 1
4 3 1
4 5 2
5 1 1
5 2 1
5 3 1
5 4 1

1-2-4-3-5

4 6 1 1 4
2 4 2
1 3 2
1 2 1
1 4 3
2 3 1
3 4 1

1-2-3-4

3 3 5 1 3
1 2 1
2 3 1
1 3 1

No

Hint

In the first example, there are $5$ cities and all possible roads exist. There are $5$ simple paths from city $1$ to city $5$, sorted as follows:

• 20% of the testdata: $n \le 5$.
• 40% of the testdata: $n \le 30$.
• 100% of the testdata: $2 \le n \le 50$, $1 \le k \le 200$, $1 \le l \le 10^4$.

Translated by ChatGPT 5