成对付费

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个有 $n$ 个城市、$m$ 条无重边的无向带权图。每条道路有权值 $w$。

旅行时每次必须连续经过恰好两条道路。若这两条道路的权值依次为 $x,y$，则本次费用为 $(x+y)^2$。求从城市 $1$ 到每个城市的最小费用；若不能按这种规则到达，输出 $-1$。

下图展示了样例中的图：

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示城市 $u,v$ 之间有一条权值为 $w$ 的无向道路。

输出格式

输出 $n$ 个整数。第 $i$ 个整数表示从城市 $1$ 到城市 $i$ 的最小费用；若无法到达，输出 $-1$。

样例输入 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

数据范围

$2\le n\le 10^5$，$1\le m\le\min\{n(n-1)/2,2\times10^5\}$，$1\le w\le 50$。图中无自环和重边，但不保证连通。