题目描述

john的农场中有n块农田编号为1至n，农田之间有m条双向连通的道路，现在john想从农田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