C--最短路

Time Limit: 7000 ms Memory Limit: 65536 KiB

Problem Description

给出一个带权无向图,包含n个点,m条边。求出s,e的最短路。保证最短路存在。

Input

 多组输入。

对于每组数据。

第一行输入n,m(1<= n && n<=5*10^5,1 <= m && m <= 3*10^6)。
接下来m行,每行三个整数,u,v,w,表示u,v之间有一条权值为w(w >= 0)的边。
最后输入s,e。

Output

 对于每组数据输出一个整数代表答案。

Sample Input

3 1
1 2 3
1 2

Sample Output

3

Hint

Source

zmx