509009 - N条边的最短路

【题目描述】N条边的最短路(n)

给定一个由T(2≤T≤100)条边构成的无向图,点的编号为1~2000之间的整数,求由起点S到终点E正好经过N(2≤N≤1000000)条边(可以重复经过)的最短路。

输入

第一行4个整数N,T,S和E。 随后2~T+1行:描述每条边的长和两个点的编号。

输出

输出一个整数表示答案。

样例

输入

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出

10
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题