345. 牛站

给定一张由T条边构成的无向图,点的编号为1~1000之间的整数。

求从起点S到终点E恰好经过N条边(可以重复经过)的最短路。

注意: 数据保证一定有解。

输入格式

第1行:包含四个整数N,T,S,E。

第2..T+1行:每行包含三个整数,描述一条边的边长以及构成边的两个点的编号。

输出格式

输出一个整数,表示最短路的长度。

数据范围

$2 \le T \le 100$,
$2 \le N \le 10^6$

输入样例:

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

输出样例:

10