以下题面由 AI 翻译。

题目描述

Stanley 居住在一个由 $n$ 个城市组成的国家（他住在城市 $1$）。城市之间有一些双向道路，已知每条道路的行驶时间。此外，每对城市之间有一个航班，从城市 $u$ 到城市 $v$ 的航班需要 $(u - v)^2$ 的时间。由于 Stanley 最近看了《萨利机长》，他对飞行非常恐惧，因此最多只能乘坐 $k$ 次航班。Stanley 想知道从城市 $1$ 出发到每个城市的最小旅行时间。

输入格式

输入的第一行包含三个整数 $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}$）——道路连接的两个城市及行驶所需时间。注意，某些城市之间可能有不止一条道路。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示到达城市 $i$ 的最小时间。

样例数据

3 1 2
1 3 1

0 1 1

4 3 1
1 2 3
2 4 5
3 4 7

0 1 4 6

2 1 1
2 1 893746473

0 1

5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1

0 1 2 2 3

提示

第一个样例解释
到达城市 $1$ 的时间为 $0$；到城市 $2$ 可以乘坐一次航班（时间 $1$ 单位）；到城市 $3$ 可以直接通过道路（时间 $1$ 单位）。

第二个样例解释
到达城市 $1$ 的时间为 $0$。到城市 $2$ 的最佳方式是乘坐航班（时间 $1$ 单位）。到城市 $3$ 的路径是：从城市 $1$ 乘车到城市 $2$（时间 $3$ 单位），然后乘坐航班到城市 $3$。到城市 $4$ 的路径是：先乘坐航班到城市 $2$，再乘车到城市 $4$（时间 $5$ 单位）。

数据范围

• $2 \leq n \leq 10^{5}$
• $1 \leq m \leq 10^{5}$
• $1 \leq k \leq 20$
• 道路时间 $1 \leq w \leq 10^{9}$
• 输入保证所有数值均为整数。