随机次短路
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
输入$n$个点，$m$条边, 每条边的权值为$w$
接下来输入两个整数代表两个点，让你求出这两点间的次短路
次短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度
输入格式
第一行输入两个整数$n, m$ $(1 < n \le 5*10^4)$,$(n - 1 \le m \le 2*10^5)$ 接下来 $m$ 行 每一行有三个数 $u,v,w$ $(1 \le u,v \le n)$,$(1 \le w \le 3e4)$,代表点$u$到点$v$之间有一条权值为 $w$ 的单向边 最后一行两个整数 $x, y$ ,$(1 \le x,y \le n)$ 代表两个点 保证图联通
输出格式
输入一个数表示两点之间的距离
样例
5 6
1 2 1
2 3 2
3 4 3
4 5 4
1 4 5
3 5 2
1 5
9
来源
2022 HGNU-SWUT暑假联合集训