No submission language available for this problem.

题目描述

小码君是一个年轻的农场主，他继承了他祖父的农场，农场中有 $n$ 块农田编号为 $1$ 至 $n$，农田之间有 $m$ 条双向连通的道路，但他并不像他祖父那样擅长种植农作物。他在农场里建起了一座小屋，并开始研究如何使用计算机来帮助他管理农场。

有一天，小码君想要从他的农田 $S$ 移动到另一个农田 $T$ ，但他并不知道最短的路径是什么。他知道这是一个经典的计算机科学问题，因此他决定编写一个程序来解决它。他希望这个程序可以帮助他找到最短的路径，从而更高效地管理他的农场。

输入格式

第一行四个由空格隔开的整数，分别表示 $n，m，S，T$

第二行开始的 $m$ 行，每行三个正整数 $a，b，c$，表示一条从 $a$ 农田到 $b$ 农田长度为 $c$ 的边。

输出格式

一个整数表示从 $S$ 到 $T$ 的最短路长度。数据保证至少存在一条道路。

样例 #1

样例输入 #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

提示

$1<=n<=2500$

$1<=m<=6500$

$1<=a,b<=n$

$1<=c<=10000$