Олеся решила отправиться в путешествие по стране, состоящей из \(n\) городов (она живет в городе \(1\)). Между некоторыми городами страны есть двусторонние дороги. Для каждой дороги известно время, необходимое для того, чтобы по ней проехать. Также между каждой парой городов есть авиарейс, перелет из города \(u\) в город \(v\) занимает \((u - v)^2\) времени.
Олеся недавно посмотрела «Чудо на Гудзоне» и несколько боится летать, поэтому она может воспользоваться не более чем \(k\) перелетами. Олеся хочет узнать минимальное время путешествия в каждый из \(n\) городов страны из города \(1\).
Выходные данные
Выведите \(n\) чисел, \(i\)-е из которых равно минимальному времени путешествия в город \(i\).
Примечание
В первом примере время путешествия до города 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 единиц времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 2
1 3 1
|
0 1 1
|
|
2
|
4 3 1
1 2 3
2 4 5
3 4 7
|
0 1 4 6
|
|
3
|
2 1 1
2 1 893746473
|
0 1
|
|
4
|
5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1
|
0 1 2 2 3
|