【例题5】最短路径

题目描述

给出一个无向图，起点 $s$ ，终点 $e$ ， $t$ 条边和一个正整数 $n$ ，求从 $s$ 到 $e$ 走过 $n$ 条边的最短路径长度。

第一行四个正整数 $n$ ， $t$ ， $s$ ， $e$ 。

接下来 $t$ 行，每行三个正整数 $w$ ， $x$ ， $y$ ，表示一条连接 $x$ 和 $y$ 的权值为 $w$ 的边。

输出一个正整数，表示最短路径长度。

对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^{6}$ ， $2 < t < 100$ ， $1 \leq s$ ， $e$ ， $w$ ， $x$ ， $y \leq 1000$ 。