题目描述

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

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

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

输入

第1行:包含四个整数$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

提示

$2 \leq T \leq 100$

$2 \leq N \leq 10^6$