该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个无向图，求有 $A$ 点到 $B$ 点的最短路径。

输入格式

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

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

接下来m行，x，y，w

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

输出格式

一个数，表示 $a$ 到 $b$ 的最短路

样例

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

数据范围与提示

$1 \le n \le 2500$

$1 \le m \le 6200$

$1 \le a,b \le n$