## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ cities (he lives in city $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$ and $v$ takes $\left(u-v{\right)}^{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 $1$.

Input

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

Solution Click Below:-  👉
👇👇👇👇👇

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\le u,v\le n$$u\ne v$$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$ integers, $i$-th of which is equal to the minimum time of traveling to city $i$.