﻿ Fuzhou University OnlineJudge ﻿
Problem 1610 Just for rescue

## 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
﻿