Stanley 生活在一个由 $$$n$$$ 个城市组成的国家(他住在 $$$1$$$ 城市)。有些城市之间有双向道路,您知道骑车穿过每个城市需要多长时间。此外,每对城市之间都有一个航班,城市 $$$u$$$ 和 $$$v$$$ 之间的航班需要 $$$(u - v)^2$$$ 时间。
Stanley因为最近看了《萨利机长:哈德逊河奇迹》,对坐飞机相当害怕,所以他最多只能乘坐$$$k$$$航班。 Stanley 想知道从 $$$1$$$ 城市到每个 $$$n$$$ 城市的最短旅行时间。
输入
输入的第一行有三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — 城市数量,道路数量,以及斯坦利可以乘坐的最大航班数量。
以下 $$$m$$$ 行描述了道路。每个包含三个整数 $$$u$$$、$$$v$$$、$$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) - 道路连接的城市以及骑行所需的时间。请注意,某些城市对可能由多条道路连接。
输出
打印 $$$n$$$ 整数,其中 $$$i$$$ 等于前往城市 $$$i$$$ 的最短时间。
示例
输入 #1
3 1 2 1 3 1
输出 #1
0 1 1
输入 #2
4 3 1 1 2 3 2 4 5 3 4 7
输出 #2
0 1 4 6
输入 #3
2 1 1 2 1 893746473
输出 #3
0 1
输入#4
5 5 2 2 1 33 1 5 93 5 3 48 2 3 21 4 2 1
输出#4
0 1 2 2 3
注意
在第一个样本中,到达城市 1 不需要时间;要到达城市 2,可以乘坐 1 和 2 之间的航班,需要 1 个单位时间;您可以从城市 1 通过一条道路到达城市 3,这将需要 1 个单位时间。
在第二个示例中,到达城市 1 也不需要时间。要到达城市 2 Stanley,应使用 1 和 2 之间的航班,这将花费 1 个时间单位。要到达城市 3,斯坦利可以乘坐城市 1 和 2 之间的航班,需要 3 个单位时间,然后乘坐 2 和 3 之间的航班。要到达城市 4 斯坦利,应该乘坐城市 1 和 2 之间的航班,然后乘坐从 2 到 4 的航班,需要 5 个单位时间。