Your task is to find the $k$ shortest flight routes from Syrjälä to Metsälä. A route can visit the same city several times.

Note that there can be several routes with the same price and each of them should be considered (see the example).

Input

The first input line has three integers $n$, $m$, and $k$: the number of cities, the number of flights, and the parameter $k$. The cities are numbered $1,2,\ldots,n$. City 1 is Syrjälä, and city $n$ is Metsälä.

After this, the input has $m$ lines describing the flights. Each line has three integers $a$, $b$, and $c$: a flight begins at city $a$, ends at city $b$, and its price is $c$. All flights are one-way flights.

You may assume that there are at least $k$ distinct routes from Syrjälä to Metsälä.

Output

Print $k$ integers: the prices of the $k$ cheapest routes sorted according to their prices.

Constraints

• $2 \le n \le 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $1 \le a,b \le n$
• $1 \le c \le 10^9$
• $1 \le k \le 10$

Example

Input:

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

Output:

4 4 7

Explanation: The cheapest routes are $1 \rightarrow 3 \rightarrow 4$ (price $4$), $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ (price $4$) and $1 \rightarrow 2 \rightarrow 4$ (price $7$).