CF1486E.Paired Payment

There are $n$ cities and $m$ bidirectional roads in the country. The roads in the country form an undirected weighted graph. The graph is not guaranteed to be connected. Each road has it's own parameter $w$. You can travel through the roads, but the government made a new law: you can only go through two roads at a time (go from city $a$ to city $b$ and then from city $b$ to city $c$) and you will have to pay $(w_{ab} + w_{bc})^2$ money to go through those roads. Find out whether it is possible to travel from city $1$ to every other city $t$ and what's the minimum amount of money you need to get from $1$ to $t$.

该国共有 $n$ 座城市和 $m$ 条双向道路。这些道路构成一个无向带权图。该图不一定连通。每条道路都有其自身的权重参数 $w$。你可以沿道路通行，但政府颁布了一项新法规：每次出行仅允许连续经过两条道路（即从城市 $a$ 到城市 $b$，再从城市 $b$ 到城市 $c$），且通行这两条道路需支付 $(w_{ab} + w_{bc})^2$ 的费用。请判断是否可以从城市 $1$ 到达其余每个城市 $t$，并求出从城市 $1$ 到达城市 $t$ 所需的最少费用。

First line contains two integers $n$, $m$ ($2 \leq n \leq 10^5$, $1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$).

Next $m$ lines each contain three integers $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$). It's guaranteed that there are no multiple edges, i.e. for any edge $(u_i, v_i)$ there are no other edges $(u_i, v_i)$ or $(v_i, u_i)$.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$1 \leq m \leq \min\left(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5\right)$）。

接下来的 $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)$。

For every city $t$ print one integer. If there is no correct path between $1$ and $t$ output $-1$. Otherwise print out the minimum amount of money needed to travel from $1$ to $t$.

对于每个城市 $t$，输出一个整数。如果城市 $1$ 与城市 $t$ 之间不存在合法路径，则输出 $-1$；否则输出从城市 $1$ 到城市 $t$ 所需的最少金额。

The graph in the first example looks like this.

In the second example the path from $1$ to $3$ goes through $2$, so the resulting payment is $(1 + 2)^2 = 9$.

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

在第二个样例中，从节点 $1$ 到节点 $3$ 的路径经过节点 $2$，因此最终支付金额为 $(1 + 2)^2 = 9$。