题目描述

 在$N$个点$M$条边的无向图中，每条边有各自的距离，你在起点$S$，你需要走小于等于一百条边到达终点$T$，试求最短的距离，如果无法在百边之内到达$T$输出$-1$。

输入格式

第一行，四个整数$N,M,S,T(1≤N≤10^4; 1≤M≤10^5; 1≤S,T≤N)$。

接下去$M$行，每行三个整数$u,v,w(1≤u,v≤N; 1≤w≤10^9)$，表示$u$、$v$之间有一条距离为$w$的边。

输出格式

如果能从$S$点出发百边之内到达$T$，输出一个整数表示最短的距离；否则输出$-1$。

样例

4 6 1 4
1 2 3
1 3 2
1 4 3
2 3 2
2 4 4
3 4 1

3

来源

2022 HGNU-SWUT暑假联合集训