题目描述
给出一个无向图，起点 $s$，终点 $e$，$t$ 条边和一个正整数 $n$，求从 $s$ 到 $e$ 走过 $n$ 条边的最短路径长度。
输入
第一行四个正整数 $n,t,s,e$。
接下来 $t$ 行，每行三个正整数 $w,x,y$，表示一条连接 $x$ 和 $y$ 的权值为 $w$ 的边。
输出
输出一个正整数，表示最短路径长度。
样例输入输出
输入#1
复制
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
提示
对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^6$，$2 \leq t \leq 100$，$1 \leq s,e,w,x,y \leq 1000$。