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

問題

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

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

• G の辺集合から辺を 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

制約

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq u_i < v_i \leq N
• i \neq j ならば u_i \neq u_j または v_i \neq v_j
• 1 \leq w_i \leq 10^9

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

出力形式

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

u v

• u, v は整数
• 1 \leq u, v \leq N

入力例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

Note

Link

 

---