509009 - N条边的最短路

【题目描述】N条边的最短路（n）

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

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

输出一个整数表示答案。