Paired Payment

题意翻译

给定图 $G=\lang V,E\rang$（不一定保证 $G$ 是一个连通图），请你找到从 $1$ 开始到达任意一个点 $t(t\in [1,n])$ 的最短路长度。 但是每次你不能只走 $E$ 中的一条边，而是选择两条边 $e_1,e_2\in E\;\text{s.t.}\;e_1=\lang x,u,w_1\rang,e_2=\lang u,y,w_2\rang$，然后，执行 $x\overset{e_1}\rightarrow u\overset{e_2}\rightarrow y$ 且每次走的花费是 $(w_1+w_2)^2$. 保证 $|V|\le 10^5,|E|\le \min\left\{2\times 10^5,{|V|\times (|V|-1)\over 2}\right\},\forall e=\lang u,v,w\rang \in E,w\le 50$.

题目描述

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 $ .

输入输出格式

输入格式

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) $ .

输出格式

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 $ .

输入输出样例

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

说明

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 $ . 

题意翻译

给定图 $G=\lang V,E\rang$（不一定保证 $G$ 是一个连通图），请你找到从 $1$ 开始到达任意一个点 $t(t\in [1,n])$ 的最短路长度。 但是每次你不能只走 $E$ 中的一条边，而是选择两条边 $e_1,e_2\in E\;\text{s.t.}\;e_1=\lang x,u,w_1\rang,e_2=\lang u,y,w_2\rang$，然后，执行 $x\overset{e_1}\rightarrow u\overset{e_2}\rightarrow y$ 且每次走的花费是 $(w_1+w_2)^2$. 保证 $|V|\le 10^5,|E|\le \min\left\{2\times 10^5,{|V|\times (|V|-1)\over 2}\right\},\forall e=\lang u,v,w\rang \in E,w\le 50$.