题目描述

输入$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暑假联合集训