[Solution] Long Way Home Codeforces Solution

E. Long Way Home

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Stanley lives in a country that consists of n$n$ cities (he lives in city 1$1$). 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$u$ and v$v$ takes (u−v)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$k$ flights. Stanley wants to know the minimum time of a journey to each of the n$n$ cities from the city 1$1$.

Input

In the first line of input there are three integers n$n$, m$m$, and k$k$ (2≤n≤105$2\le n\le {10}^5$, 1≤m≤105$1\le m\le {10}^5$, 1≤k≤20$1\le k\le 20$) — the

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following m$m$ lines describe the roads. Each contains three integers u$u$, v$v$, w$w$ (1≤u,v≤n$1\le u,v\le n$, u≠v$u\ne v$, 1≤w≤109$1\le w\le {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$n$ integers, i$i$-th of which is equal to the minimum time of traveling to city i$i$.