题目描述

贝茜在田野里，她想回到谷仓，以便在农夫约翰叫她早起挤奶之前尽可能多地睡会儿觉。贝茜需要她的美容觉，所以她想尽快回到谷仓。

农夫约翰的田野里有(N)（(2 ≤ N ≤ 1000)）个地标，每个地标都有唯一的编号(1)到(N)。地标(1)是谷仓；贝茜一整天待着的苹果树林是地标(N)。奶牛们在田野里通过(T)（(1 ≤ T ≤ 2000)）条双向的牛径在各个地标之间移动，这些牛径长度各不相同。贝茜对自己的导航能力没有信心，所以一旦她开始走一条牛径，她就会从这条牛径的起点一直走到终点。 给定这些地标之间的牛径信息，确定贝茜回到谷仓必须行走的最小距离。可以保证一定存在这样的一条路线。

输入

第(1)行：两个整数：(T)和(N)

第(2)行到(T + 1)行：每行用三个空格分隔的整数描述一条牛径。前两个整数是这条牛径连接的两个地标。第三个整数是这条牛径的长度，范围是(1)到(100)。

输出

第(1)行：一个整数，即贝茜从地标(N)到地标(1)必须行走的最小距离。

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

90

提示

输入细节： 有五个地标。

输出细节： 贝茜可以沿着牛径(4)、(3)、(2)和(1)回到家。

来源

USACO 2004 November