题目描述

给定一张由$\red {T}$条边构成的无向图，点的编号为$\red {1\sim 1000}$之间的整数。

求从起点$\red {S}$到终点$\red {E}$恰好经过$\red {N}$条边（可以重复经过）的最短路。

输入格式

第$\red {1}$行：包含四个整数$\red {N，T，S，E}$。

第$\red {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

提示

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

$\red {2≤T≤100}$,

$\red {2≤N≤10^6}$