Maksym, Petro and Bohdan

Limits: 2 sec., 256 MiB

Competitive programmers Maksym, Petro and Bohdan can’t imagine their life without trainings. They live in the country U. U is a very strange country where all roads have a unique length. Also U’s government quarantines one city and closes all roads that connect it with other cities every day.

Maksym and Petro are never late for trainings at the university, but Bohdan... Bohdan loves to sleep! When he wakes up, he watches the news to find out which city is quarantined and starts wandering around the country on the way to the university. Actually, he visits all the opened cities going through the minimum possible number of distinct roads so that the length of all the roads which he passes was minimal possible. This is because he hurries for the training! If he can’t visit all the opened cities he stays at home.

Maksym and Petro are desperate to find Bohdan. They decided to wait for him on two different roads so that they can meet Bohdan on one of them for sure.

Maksym and Petro are experienced competitive programmers but due to the Bohdan’s absence they are confused and can’t find such roads. In addition, Maksym and Petro didn’t watch the news in the morning so they don’t know which city is quarantined. Help them to choose two roads where they can wait for Bohdan regardless of government decision.

Input

The first line contains two integers \(n\) and \(m\) - number of cities and roads.

Following \(m\) lines contains three integers \(a_{i}, b_{i}, c_{i}\) — cities \(a_{i}\) and \(b_{i}\) are connected by road \(i\) with length \(c_{i}\).

Output

Print indices of two roads.

Constraints

\(2 \le n \le 10^{5}\),

\(2 \le m \le 10^{5}\),

\(1 \le a_{i} \le n\),

\(1 \le b_{i} \le n\),

\(1 \le c_{i} \le 10^{6}\),

all \(c_i\) are distinct.

Samples