E: 均衡な辺削除 (Balanced Edge Deletion)

問題

N 頂点 M 辺の重み付き単純無向グラフ G が与えられる。 頂点には 1 から N、 辺には 1 から M の番号がつけられている。 i 番目の辺は頂点 u_i と v_i を結んでおり、そのコストは w_i である。

このグラフに対して、以下の操作を 1 度だけ行うことを考える。

上の操作によってグラフが分割されることがあるので、操作後のグラフを A, B と表記することとする。(分割されない場合、B は空グラフであるとする。) W(X) をグラフ X 内にある辺のコストの総和 (グラフに辺が存在しない場合 W(X)=0) とし、$\mathrm{cost}$(A,B)=|W(A)−W(B)| と定義する。$\mathrm{cost}$(A,B) が最小になるような辺 (u,v) を求めよ。複数存在する場合は、u が最小であるものを答えよ。それでも複数存在する場合は、v が最小であるものを答えよ。

入力形式

入力は以下の形式で与えられます。

N M
u_1 v_1 w_1
...
u_M v_M w_M

制約

与えられるグラフは連結である。

出力形式

答えとなる辺を以下のように空白区切りで一行に出力せよ。

u v

入力例1

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

出力例1

2 3

入力例2

10 11
1 2 1
2 3 10
1 5 2
3 4 7
3 5 9
5 6 8
6 7 5
6 8 3
7 8 12
7 9 1
9 10 8

出力例2

5 6