Description

Tom is a student in Shan Dong Normal University! his University in the suburbs,this day,Tom wanted to go to the downtown to visit his old friend Jerry,But tom faced a problem ,he want to know how to reach the city center fastest,now the bus stations of city are $n[2,100]$, there are $m[1,1000]$ bus routes in the city

Tom in the $1$st bus station,Jerry in the $N$th bus station

Format

Input

The fist line is $m,n$;

Next $m$ lines is $a,b,c$ ($a,b$ is the name of bus station , $c$ is the time you cost from station $a$ to station $b$)

Output

The shortest time tom reach city center

Samples

1 2
1 2 10
3 4
1 2 10
2 3 10
3 4 10

10
30