#P11770. [2023年联测]走路

    ID: 10921 传统题 2000ms 512MiB 尝试: 11 已通过: 2 难度: 8 上传者: 标签>图论树算法LCACF2400最小生成树并查集线段树模拟搜索

[2023年联测]走路

走路 (walk)

题目描述

EFZ 的校园可以抽象成一张nn个点mm条边的无向图,边带权。wygz 初始站在11 号点,她想要去找站在 ii 号点的 ix35。

wygz 不想走重复的边,但她觉得走重复的点是可以接受的。定义一条路径的权值是这条路径上边权的最大值与最小值的和。

对于每个 2≤i≤n2\le i\le n,wygz 想知道以 11 为起点、ii 为终点的路径权值最小是多少。

输入格式

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

接下来mm 行,每行三个整数x,y,zx,y,z,表示一条边连接x,yx,y两点,边权为zz。允许边权为0。

输出格式

共n−1n-1 行,对于2≤i≤n2 \leq i \leq n 依次输出答案。若某点从点1不可达,对应输出 -1。

样例输入 1

3 3
1 2 2
1 3 1
2 3 1

样例输出 1

2
2

样例输入 2

7 10
1 2 2
1 2 8
2 3 3
3 4 5
3 5 4
4 5 4
6 5 7
6 4 4
1 7 6
6 7 9

样例输出 2

4
5
6
6
6
10

样例输入 3

4 4
1 2 2
3 2 0
2 4 3
4 3 1

样例输出 3

3
2
2

大样例

见下发文件,其中 walk .in/out 表示满足相应 Subtask 的限制

数据范围

保证 1≤x,y≤n1\le x,y\le n,x≠yx\ne y,0≤z≤1090\le z\le10^9。

子任务 nn 上界 mm 上界 特殊限制 分值
1 3×1053\times10^5 m=n−1m=n-1 9
2 与点 1 相连的边权为 0 17
3 与点 1 相连的边权为 10910^9 12
4 10 无重边 9
5 20 6
6 2000 所有边满足 ∣x−y∣=1\lvert x-y\rvert=1
7 无 9
8 5000 3×1053\times10^5 8
9 3×1053\times10^5 依赖前面所有子任务 24