提示: 欢迎访问OurACM平台。
Problem 1610 Just for rescue

Accept: 85    Submit: 238
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei is forgetful, and he can not remember the path he has gone through! So he is usually lost in large city. Oaiei now is lost in the city A. A city has a total of N sites, each site is number from 1 to N. Oaiei is in the site t, your location is in the site s, given you the time cost between the N sites. Oaiei hopes you can find a path to find him as soon as possible, and he want to go home.

Input

There are multiply tests. For each test, the first line are two integer N (3 <= N <= 100000) and M (3 <= M <= 100000), N is the number of sites and M is the number of path between sites. Following M lines, each line has three positive integers a, b, c (1<=a,b<=N), indicate you should spend time c from site a to site b. Note that there are not multi-edges between a to b and you can not spend c time form site b to site a.

Output

The last line is two integer t and s, Oaiei is in the site t and you are in the site s.

Sample Input

4 4 1 2 1 2 3 1 1 4 1 4 3 1 3 1 5 5 1 2 1 2 5 1 5 3 1 1 4 2 4 3 1 3 1

Sample Output

2 1->2->3 3 1->4->3

Source

FOJ月赛-2008年5月

Submit  Back  Status  Discuss