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

题目描述

给定一个无向图。

求有 ${A}$ 点到 ${B}$ 点的最短路径。

输入格式

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

$n$个顶点

$m$条边

$a$为起点

$b$为终点

接下来${2 \sim m+1}$ 行，每行$3$个正整数。代表$v$到$u$的权值是$w$

输出格式

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

样例

输入样例

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

输出样例

7

数据范围与提示

${1 \le n \le 3000}$

${1 \le m \le 6200}$

${1 \le a,b \le n}$