CF1715E.Long Way Home

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

斯坦利居住在一个由 $n$ 座城市组成的国家中（他住在第 $1$ 号城市）。某些城市之间存在双向道路，且你知道通过每条道路所需的时间。此外，任意两座城市之间都有一条航班，城市 $u$ 与城市 $v$ 之间的航班耗时为 $(u - v)^2$。

由于最近观看了电影《萨利机长：哈德逊奇迹》，斯坦利对乘飞机感到十分恐惧，因此他最多只能乘坐 $k$ 次航班。斯坦利希望知道从第 $1$ 号城市出发，到达其余 $n$ 座城市的最短时间。

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.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq n \leq 10^{5}$，$1 \leq m \leq 10^{5}$，$1 \leq k \leq 20$），分别表示城市的数量、道路的数量以及 Stanley 最多可乘坐的航班次数。

接下来的 $m$ 行描述了这些道路。每行包含三个整数 $u$、$v$、$w$（$1 \leq u, v \leq n$，$u \neq v$，$1 \leq w \leq 10^{9}$），表示该道路连接的城市编号以及通过该道路所需的时间。注意：某些城市对之间可能存在多条道路。

Print $n$ integers, $i$-th of which is equal to the minimum time of traveling to city $i$.

输出 $n$ 个整数，其中第 $i$ 个整数等于到达城市 $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.

在第一个样例中，到达城市 1 所需时间为 0；到达城市 2 可通过城市 1 与城市 2 之间的航班，耗时 1 单位时间；到达城市 3 可通过城市 1 与城市 3 之间的道路，耗时 1 单位时间。

在第二个样例中，到达城市 1 所需时间同样为 0。要到达城市 2，Stanley 应使用城市 1 与城市 2 之间的航班，耗时 1 单位时间。要到达城市 3，Stanley 可先在城市 1 与城市 2 之间乘车，耗时 3 单位时间，再使用城市 2 与城市 3 之间的航班。要到达城市 4，Stanley 应先使用城市 1 与城市 2 之间的航班，再从城市 2 乘车至城市 4，耗时 5 单位时间。