acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem F

避難所

あなたの住む市の市議会は,災害時のための避難所を一つ建設することを決定した. 避難所は,災害によって道路が寸断されるような状況であっても, 市内のできるだけ多くの地点から到達可能であることが望ましい. 市の道路網が与えられるので,最適な建設候補地を見つけて欲しい.

道路網は,無向グラフとして与えられる.市内の地点がグラフの頂点であり, 辺は地点同士を結ぶ双方向の道である. また,それぞれの道には,災害に対する推定強度を示す正の整数が与えられている. 推定強度 s の道は,災害レベル s 未満の災害時には通行可能だが, s 以上の災害が発生すると通れなくなると推定されている.

避難所としての適切さの度合いは,以下の順序関係によって評価するものとする. 災害レベル s の災害発生時に通行可能な道で地点 v まで到達できる地点の数を rs(v) とする. 地点 u と地点 v について,ある k ≥ 1 があって,

  • r1(u) = r1(v),
  • r2(u) = r2(v),
  • ...
  • rk-1(u) = rk-1(v),
  • rk(u) > rk(v)
が成り立つとき,かつそのときに限り,地点 u の方が v よりも避難所に適しているとする. この基準に基づいて,避難所として最適な地点 (同評価の地点が複数あればその全て) を求めて欲しい.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n m
a1 b1 s1
...
am bm sm

n は 105 以下の正の整数であり,地点の数を表す. m は 105 以下の非負整数であり,道の数を表す. 各地点には 1 から n までの識別番号が振られている. i 番目の道は地点 aibi を結んでおり, その推定強度は si である. ai, bi, si はそれぞれ整数であり, 1 ≤ ai < bin および 1 ≤ si ≤ 105 を満たす. ij のとき,aiaj または bibj である. 与えられるグラフは連結である. すなわち,任意の二つの地点を結ぶ経路が存在する.

入力の終わりは二つのゼロからなる行で表される. データセットの個数は 50 を超えない.

Output

各データセットについて上述の基準に照らして最適である地点 (同評価の地点が複数あればその全て) の地点識別番号のリストを,1 行に空白区切りで小さい順に出力せよ.

Sample Input

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

Output for the Sample Input

2 3
1 2 3
3 4 5
(End of Problem F) A B C D E F G H