[usaco2007 Nov]relays 奶牛接力跑

FJ 的 $N$ 头奶牛选择接力跑作为日常锻炼项目。她们将在牧场现有的 $T$ 条跑道上进行接力跑。

牧场中的跑道之间存在若干交汇点。每条跑道连接两个不同的交汇点 $I1_i$ 和 $I2_i$ ，长度为 $\mathit{length}_i$ 。每个交汇点都至少是两条跑道的端点，且任意两个交汇点之间至多有一条跑道直接相连。因此，可以将交汇点视为顶点，将跑道视为无向边，从而构成一张图。

在接力跑开始前，所有 $N$ 头奶牛都要站在某个交汇点上，同一个交汇点可以有多头奶牛。她们的站位必须保证接力棒能够依次传递，并且最后持棒的奶牛停在预设的终点。

给定接力跑的起点 $S$ 和终点 $E$ ，请计算从 $S$ 到 $E$ 、恰好经过 $N$ 条跑道的路径的最小总长度。

输入格式

第一行包含 $4$ 个以空格分隔的整数 $N,T,S,E$ ，分别表示奶牛数量、跑道数量、起点编号和终点编号。

接下来 $T$ 行，第 $i$ 行包含 $3$ 个以空格分隔的整数 $\mathit{length}_i,I1_i,I2_i$ ，表示第 $i$ 条跑道的长度及其连接的两个交汇点编号。

输出一个正整数，表示从起点 $S$ 到终点 $E$ 、恰好经过 $N$ 条跑道的路径的最小总长度。

本题为 USACO 2007 年 11 月试题「Relays」，题面与测试数据整理自 BZOJ 1706。