题目背景

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

题目描述

有一个 $n$ 个点 $m$ 条边的有向图，每条边有边权。保证 $1$ 号点能到达所有点。

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

输入格式

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

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

输出格式

共 $n-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\%$ 有：$n\leq 8, m\leq 15$ 。

对于前 $30\%$ 有：$n\leq 100, m\leq 300$ 。

对于前 $60\%$ 有：$n\leq 1000, m\leq 3000$ 。

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