题目描述

有一个 $n$ 个点 $m$ 条边的无向图，请求出从 $s$ 到 $t$ 的最短路长度。

输入格式

第一行四个正整数 $n,m,s,t$。 接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接 $u,v$，长为 $w$ 的边。

输出格式

输出一行一个整数，表示答案。

数据范围与约定

对于 $100\%$ 的数据，$1\le n \le 2500$，$1\le m \le 6200$，$1\le w \le 1000$。

可见测试数据

输入数据 1

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

输出数据 1

7

输入数据 2

5 8 1 5
1 2 11
2 3 1
3 4 17
4 5 6
2 4 3
1 4 24
2 5 16
1 3 29

输出数据 2

20

输入数据 3

6 11 1 6
1 2 1
2 3 6
3 4 1
4 5 15
5 6 5
1 4 10
1 5 29
2 6 28
1 3 16
3 5 15
2 5 15

输出数据 3

21