Problem Description

There are $n$ cities and $m$ one-way roads, with city numbers ranging from $1$ to $n$. Each road connects two distinct cities, and no two roads share the same origin or destination, thus satisfying $m \le n(n-1)$.

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

Input Format

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

The following $m$ lines each contain three integers $u, v, l$, indicating a one-way 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: list each city visited from city $a$ to city $b$, separated by a hyphen -.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1-2-4-3-5

Sample Input #2

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

Sample Output #2

1-2-3-4

Sample Input #3

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

Sample Output #3

No

Notes

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 data satisfies: $n \leq 5$;
• $40\%$ of the data satisfies: $n \leq 30$;
• $100\%$ of the data satisfies: $2 \leq n \leq 50$, $1 \leq k \leq 200$, $1 \le l \le 10^4$.

见题面 Input 部分

见题面 Output 部分