#YDSP2024SD. 最短路的一集

最短路的一集

题目背景

众所周知,一场比赛需要有一点压轴题。于是,它来了。

题目描述

有一个 nn 个点 mm 条边的有向图,每条边有边权。保证 11 号点能到达所有点。

对于每个点 uu,请你求出从 11 号点出发到达 uu 的两条没有公共边的路径,并且要求边权和最小。

输入格式

第一行两个整数 n,mn,m

接下来 mm 行,每行三个整数 u,v,wu,v,w 表示一条从 uuvv 的边权为 ww 的有向边。保证没有重边和自环。

输出格式

n1n-1 行,每行一个整数表示答案。

对于一个点,如果不存在两条没有公共边的路径,那么输出 1-1

样例输入

5 7
1 2 4
2 3 3
1 3 8
3 5 3
4 5 2
5 4 7
1 5 1

样例输出

-1
15
-1
11

附加样例

见附加文件中的 ex.zip

数据限制

对于前 10%10\% 有:n8,m15n\leq 8, m\leq 15

对于前 30%30\% 有:n100,m300n\leq 100, m\leq 300

对于前 60%60\% 有:n1000,m3000n\leq 1000, m\leq 3000

对于前 100%100\% 有:$1\leq n\leq 10^5, 0\leq m\leq 3\times 10^5, 0\leq w\leq 10^9$ 。