В стране \(n\) городов и \(m\) двунаправленных дорог. Дороги в стране формируют неориентированный взвешенный граф. Граф может быть несвязным. У каждой дороги есть свой параметр \(w\). Вы можете ездить по дорогам, но правительство издало новый закон: вы можете проезжать только по двум дорогам сразу (проехать из города \(a\) в город \(b\), и из города \(b\) в город \(c\)) и вы должны будете заплатить \((w_{ab} + w_{bc})^2\) денег, чтобы проехать по этим дорогам. Для каждого города \(t\) найдите, можно ли добраться до него из города \(1\), и какое наименьшее количество денег необходимо потратить, чтобы добраться из \(1\) в \(t\).
Выходные данные
Для каждого города \(t\) выведите одно целое число. Если нет корректного пути из \(1\) в \(t\) выведите \(-1\). Иначе выведите минимальное необходимое количество денег, чтобы добраться из \(1\) в \(t\).
Примечание
Граф в первом примере выглядит так.
Во втором примере путь из \(1\) в \(3\) проходит через \(2\), так что результирующая стоимость поездки будет \((1 + 2)^2 = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2
|
0 98 49 25 114
|
|
2
|
3 2
1 2 1
2 3 2
|
0 -1 9
|