Long Way Home
Contest: Codeforces Round 816 (Div. 2)
Difficulty rating: 2400
Tags: data structures, divide and conquer, dp, geometry, graphs, greedy, shortest paths

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$$$.

Input format:
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 format:
Print $$$n$$$ integers, $$$i$$$-th of which is equal to the minimum time of traveling to city $$$i$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
3 1 2
1 3 1

Example output:
0 1 1

Example input:
4 3 1
1 2 3
2 4 5
3 4 7

Example output:
0 1 4 6

Editorial:
Let's assume we know the shortest distances from the first vertex to each, if we have added no more than $$$k$$$ edges (air travels). Let's learn to recalculate the answer for $$$(k + 1)$$$ edges.
First, let's update the answer for all the paths ending in an air travel. Then we can run Dijkstra to take into account all the paths ending with a usual edge.
In order to add an air travel, we need to update the distance to $$$v$$$, with all the paths ending with an air travel to $$$v$$$. To do so, we can use Convex Hull Trick, since the recalculation formula has the following form ($$$d_{old}$$$ — array of distances for $$$k$$$ edges, $$$d_{new}$$$ — array of distances if $$$k+1$$$ the flight goes exactly to the $$$i$$$-th vertex):
$$$$$$d_{new}[v] = \min\limits_{u} \ d_{old}[u] + (u - v)^2$$$$$$
After that, we need to run Dijkstra to update the distances with all the paths not ending with an air travel.
The resulting asymptotics is $$$O(k(m \log n + n))$$$