给出 nnn 个点 mmm 条边的无向图,求 sss 到 ttt 的最短路。
输入
第一行四个整数 n,m,s,t (1≤n≤2500,1≤m≤6200)n,m,s,t \ (1 \leq n \leq 2500,1 \leq m \leq 6200)n,m,s,t (1≤n≤2500,1≤m≤6200)。
接下来 mmm 行,每行三个数 u,v,wu,v,wu,v,w,表示 uuu 和 vvv 之间有边权为 w (1≤u,v≤n,1≤w≤109)w \ (1 \leq u,v \leq n,1 \leq w \leq 10^9)w (1≤u,v≤n,1≤w≤109) 的边。
输出
一个整数,表示答案。
数据保证至少存在一条道路。
样例
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