B'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 (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 1 . In the first line of input there are three integers n , m , and k ( 2 <= q n <= q 10^{5} , 1 <= q m <= q 10^{5} , 1 <= q k <= q 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 <= q u, v <= q n , u neq v , 1 <= q w <= q 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. Print n integers, i -th of which is equal to the minimum time of traveling to city i . 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. '...