Long Way Home

Description:

Input:

In the first line of input there are three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following $$$m$$$ lines describe the roads. Each contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

Output:

Print $$$n$$$ integers, $$$i$$$-th of which is equal to the minimum time of traveling to city $$$i$$$.

Sample Input:

3 1 2
1 3 1

Sample Output:

0 1 1 

Sample Input:

4 3 1
1 2 3
2 4 5
3 4 7

Sample Output:

0 1 4 6 

Sample Input:

2 1 1
2 1 893746473

Sample Output:

0 1 

Sample Input:

5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1

Sample Output:

0 1 2 2 3 

Note:

In the first sample, it takes no time to get to city 1; to get to city 2 it is possible to use a flight between 1 and 2, which will take 1 unit of time; to city 3 you can get via a road from city 1, which will take 1 unit of time.

In the second sample, it also takes no time to get to city 1. To get to city 2 Stanley should use a flight between 1 and 2, which will take 1 unit of time. To get to city 3 Stanley can ride between cities 1 and 2, which will take 3 units of time, and then use a flight between 2 and 3. To get to city 4 Stanley should use a flight between 1 and 2, then take a ride from 2 to 4, which will take 5 units of time.