#574. [模板题]单源最短路

[模板题]单源最短路

题目描述

有一个无向图,求有 AA 点到 BB 点的最短路径。

输入格式

第一行四个整数,n,m,a,bn,m,a,b

n是顶点数,m是边数,a是起点,b是终点

接下来m行,x,y,w

表示x和y之间有一条权值为w的边

输出格式

一个数,表示 aabb 的最短路

样例

intput

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

output

7

数据范围与提示

1n25001 \le n \le 2500

1m62001 \le m \le 6200

1a,bn1 \le a,b \le n