You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 所在的村庄有 $n$ 个房屋，房屋编号为 $1,2,\cdots,n$，房屋与房屋之间有 $m$ 条双向道路相连。

小 Z 想从 $1$ 号房屋走到 $i$ 号房屋，小 Z 是一个追求效率的人，因此，他每次都会走从 $1$ 到 $i$ 的最快路线。但是，现在有一个比较棘手的问题，作为小 Z 的死对头小 Y，他都会站在小 Z 通往 $i$ 号房屋最快路线上的最后一条道路的中间等待小 Z，企图阻止小 Z 到达 $i$ 号房屋。

小 Z 当然不想受到小 Y 的阻扰，因此小 Z 会选择一条略有不同的路线从 $1$ 号房屋到达 $i$ 号房屋。小 Z 想知道这些不是最快路线的新路线的最佳时间，使得小 Z 能够从 $1$ 号房屋到达 $i$ 号房屋，并且能够避开最快路线上最后一条道路中间的小 Y。

换句话说，现在有 $n$ 个点 $m$ 条边的无向图，对于任意一个节点 $i(2\le i \le n)$，小 Z 想要知道从 $1$ 号点到 $i$ 号点在不经过原来 $1$ 到 $i$ 最短路上最后一条边的前提下，$1$ 到 $i$ 的最短路。

特别地，保证 $1$ 号节点到任何一个点 $i$ 的最短路都是唯一的。

输入格式

从 path.in 文件读入数据。

第一行，两个整数 $n,m$ 表示图中的点数和边数。

接下来有 $m$ 行，每行三个整数 $u_i,v_i,w_i$ 表示有一条 $u_i$ 到 $v_i$，边权为 $w_i$ 的无向边。

输出格式

输出到 path.out 文件。

共 $n-1$ 行，第 $i$ 行表示节点 $1$ 到节点 $i+1$ 在不经过原来 $1$ 节点到 $i+1$ 节点最短路上最后一条边的前提下的最短路，如果不存在满足条件的最短路，则输出 -1。

样例

4 5 
1 2 2 
1 3 2 
3 4 4 
3 2 1 
2 4 3

3 
3 
6

样例2

点击链接 ex_path2.in 和 ex_path2.out 下载大样例 2 的输入数据和输出数据。

说明/提示

样例 1 解释

• 从 $1$ 到 $2$ 的最短路是 $1\rightarrow 2$，最快时间是 $2$，最短路上最后一条边是 $1\rightarrow 2$，现在不能经过这一条边，那么较快的路径是 $1\rightarrow 3 \rightarrow 2$，耗费时间为 $3$。
• 从 $1$ 到 $3$ 的最短路是 $1\rightarrow 3$，最快时间是 $2$，最短路上最后一条边是 $1\rightarrow 3$，现在不能经过这一条边，那么较快的路径是 $1\rightarrow 2 \rightarrow 3$，耗费时间为 $3$。
• 从 $1$ 到 $4$ 的最短路是 $1\rightarrow 2 \rightarrow 4$，最快时间是 $5$，最短路上最后一条边是 $2\rightarrow 4$，现在不能经过这一条边，那么较快的路径是 $1\rightarrow 3 \rightarrow 4$，耗费时间为 $6$。

数据范围

$20\%$ 的数据 $n \le 200, m \le 10^3$。

$50\%$ 的数据 $n \le 3000, m \le 10^5$。

$100\%$ 的数据 $n \le 10^5, m \le 2 \times 10^5$，并且 $1\le u_i,v_i \le n,w_i\le 10^5$。