3848 - Cow Relays

为了锻炼奶牛们的体能，N头（2≤N≤1000000头）奶牛决定在整个牧场上使用T条（2≤T≤100条）奶牛道路进行接力赛。

每条奶牛道路连接两个不同的交叉点（1≤I1i≤1000；1≤I2i≤1000），每个交叉点都是至少两条轨迹的终点。奶牛知道每条轨迹的长度i（1≤length i≤1000），轨迹连接的两个交叉点，它们知道没有两个交叉口是由两条不同的轨迹直接连接的。这些轨迹形成了一个数学上称为图形的结构。

为了进行接力，N头奶牛将自己定位在各个十字路口（有些十字路口可能有不止一头奶牛）。他们必须正确地定位自己，这样他们才能一头牛接一头牛地传递接力棒，最终到达正确的终点。

编写一个程序来帮助定位奶牛。找到连接起点交叉点（S）和终点交叉点（E）的最短路径，并保证恰好穿过N条奶牛道路。

* Line 1: Four space-separated integers: N, T, S, and E

* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

仅一个数字，表示最小距离。如果不能抵达，输出-1

USACO