1793 - 最短路径easy
描述

给出一张包含 n 个节点、 m 条边的无向图(无重边,无自环),请你求出图上两点 s,t 间的最短路径长度。

其中 1\leq n\leq500 ,1\leq m\leq10000  ,  任意边权 1\leq w_i \leq500 ;


输入

第一行两个数 n,m ,分别表示节点数和边数,以空格隔开;

之后 m 行,每行 3个数 u,v,w ,表示点 u 和 v间有一条权值为 w 的边;

最后一行,两个数 s,t 表示选择的两个点,以空格隔开。


输出

输出一个数,表示 s,t 间最短路径的长度。

样例

输入

4 3
1 2 6
1 3 4
2 4 2
3 4

输出

12
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 49
通过次数 36