← 返回题目列表

Codeforces · 1486/E

E. 配对付款

中文机器翻译题面 查看原题

该国有 $$$n$$$ 个城市和 $$$m$$$ 双向道路。该国的道路形成一个无向加权图。不保证该图是连通的。每条路都有自己的参数$$$w$$$。你可以走公路,但政府制定了一条新法律:你一次只能走两条路(从城市 $$$a$$$ 到城市 $$$b$$$,然后从城市 $$$b$$$ 到城市 $$$c$$$),并且你必须支付 $$$(w_{ab} + w_{bc})^2$$$ 钱才能走这些路。了解是否可以从 $$$1$$$ 城市前往其他所有城市 $$$t$$$,以及从 $$$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$$$ 所需的最低金额。

示例

输入 #1

5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2

输出 #1

0 98 49 25 114

输入 #2

3 2
1 2 1
2 3 2

输出 #2

0 -1 9

注意

第一个示例中的图表如下所示。

在第二个示例中,从 $$$1$$$ 到 $$$3$$$ 的路径经过 $$$2$$$,因此最终付款为 $$$(1 + 2)^2 = 9$$$。