E. Долгий путь домой
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Олеся решила отправиться в путешествие по стране, состоящей из $$$n$$$ городов (она живет в городе $$$1$$$). Между некоторыми городами страны есть двусторонние дороги. Для каждой дороги известно время, необходимое для того, чтобы по ней проехать. Также между каждой парой городов есть авиарейс, перелет из города $$$u$$$ в город $$$v$$$ занимает $$$(u - v)^2$$$ времени.

Олеся недавно посмотрела «Чудо на Гудзоне» и несколько боится летать, поэтому она может воспользоваться не более чем $$$k$$$ перелетами. Олеся хочет узнать минимальное время путешествия в каждый из $$$n$$$ городов страны из города $$$1$$$.

Входные данные

В первой строке находятся числа $$$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$$$.

Примеры
Входные данные
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 в 2 за 1 единицу времени; в город 3 можно добраться из города 1 по дороге за 1 единицу времени.

Во втором примере время путешествия до города 1 равно 0. Чтобы добраться в город 2, можно воспользоваться авиаперелетом из 1 в 2, занимающим 1 единицу времени. Чтобы добраться в город 3 за 4 единицы времени, можно проехать из города 1 в город 2 по дороге за 3 единицы времени, а потом воспользоваться авиаперелетом из 2 в 3. Чтобы добраться в город 4, можно воспользоваться авиаперелетом из города 1 в город 2, а потом проехать из города 2 в город 4 по дороге за 5 единиц времени.