# [Solution] Long Way Home solution codeforces

## Long Way Home solution codeforces

Long Way Home solution codeforces – Stanley lives in a country that consists of 𝑛n cities (he lives in city 11). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities 𝑢u and 𝑣v takes (𝑢𝑣)2(u−v)2 time.

Stanley is quite afraid of flying because of watching “Sully: Miracle on the Hudson” recently, so he can take at most 𝑘k flights. Stanley wants to know the minimum time of a journey to each of the 𝑛n cities from the city 11.

## [Solution] Long Way Home solution codeforces

In the first line of input there are three integers 𝑛n𝑚m, and 𝑘k (2𝑛1052≤n≤1051𝑚1051≤m≤1051𝑘201≤k≤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𝑢,𝑣𝑛1≤u,v≤n𝑢𝑣u≠v1𝑤1091≤w≤109) — 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.

Examples
input

Copy
3 1 2
1 3 1

output

Copy
0 1 1

## [Solution] Long Way Home solution codeforces

input

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

output

Copy
0 1 4 6
input

Copy
2 1 1
2 1 893746473

output

Copy
0 1
input

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

output

Copy
0 1 2 2 3

## [Solution] Long Way Home solution codeforces

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.