E. Парный платёж
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране $$$n$$$ городов и $$$m$$$ двунаправленных дорог. Дороги в стране формируют неориентированный взвешенный граф. Граф может быть несвязным. У каждой дороги есть свой параметр $$$w$$$. Вы можете ездить по дорогам, но правительство издало новый закон: вы можете проезжать только по двум дорогам сразу (проехать из города $$$a$$$ в город $$$b$$$, и из города $$$b$$$ в город $$$c$$$) и вы должны будете заплатить $$$(w_{ab} + w_{bc})^2$$$ денег, чтобы проехать по этим дорогам. Для каждого города $$$t$$$ найдите, можно ли добраться до него из города $$$1$$$, и какое наименьшее количество денег необходимо потратить, чтобы добраться из $$$1$$$ в $$$t$$$.

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

В первой строке находятся два целых числа $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$$$).

В следующих $$$m$$$ строках находятся по три целых числа $$$v_i$$$, $$$u_i$$$, $$$w_i$$$ ($$$1 \leq v_i, u_i \leq n$$$, $$$1 \leq w_i \leq 50$$$, $$$u_i \neq v_i$$$). Гарантируется, что в графе нет кратных рёбер, то есть для любого ребра $$$(u_i, v_i)$$$ не существует других рёбер $$$(u_i, v_i)$$$ или $$$(v_i, u_i)$$$.

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

Для каждого города $$$t$$$ выведите одно целое число. Если нет корректного пути из $$$1$$$ в $$$t$$$ выведите $$$-1$$$. Иначе выведите минимальное необходимое количество денег, чтобы добраться из $$$1$$$ в $$$t$$$.

Примеры
Входные данные
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 
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
0 -1 9 
Примечание

Граф в первом примере выглядит так.

Во втором примере путь из $$$1$$$ в $$$3$$$ проходит через $$$2$$$, так что результирующая стоимость поездки будет $$$(1 + 2)^2 = 9$$$.