0619 - 静かな町

時間制限 5 秒 / メモリ制限 256 MB / 得点 10 / Writer ei1417 / x 1 / 統計 /


TLE
5sec
MLE
256MB
得点
10

問題

アイヅ国では、毎年、駅伝大会が開催されています。アイヅ国にはN個の町が点在しており、それぞれ1からNまでの番号が付いています。いくつかの町の間は、互いに直接行き来できる道でつながっています。また、どの町の間もいくつかの道を辿って行き来ができます。大会のコースは、次のようにして決めます。

  • 2つの町のすべての組み合わせについて、最短経路の距離を求める。
  • それらの中で、最短経路の距離が最大になるような2つの町を、スタートの町とゴールの町とする。町の組み合わせが複数ある場合、そのうちのどれか一つを選ぶ。
  • 選ばれたスタートの町とゴールの町の間の最短経路を大会のコースとする。最短経路が複数ある場合、そのうちのどれか一つを選ぶ。

ヤマト国から来たお坊さんのトクイツは、アイヅ国のできるだけ静かな町に新しいお寺を開きたいと考えています。そのため、駅伝大会のコースに使われる可能性がない町を知りたがっています。

課題

アイヅ国の町を結ぶ道の情報が与えられたとき、駅伝大会のコースに使われる可能性がない町を 求めるプログラムを作成せよ。

入力

N R
s1 t1 d1
s2 t2 d2
.
.
.
sR tR dR

1行目に町の数N(2≦N≦1500)と、町の間を直接つなぐ道の数R(1≦R≦3000)が与えられる。続くR行に2つの町を双方向に直接つなぐ道が与えられる。siti(1≦sitiN)はi番目の道がつなぐ2つの町の番号を表し、di(1≦di≦1000)はその道の長さを表す。ただし、どの2つの町についても、それらを直接つなぐ道は高々1本とする。

時間制限

入力に対して、実行時間が6秒を超えてはならない。ただしHOJには問題作成時現在では6秒に設定できないので今回は5秒とする。

出力

与えられた道の情報に対して、駅伝大会のコースになることがない町をすべて出力する。1行目に駅伝大会のコースになることがない町の数Mを出力する。続くM行に、そのような町の番号を昇順で出力する。


入出力例

入力例1

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

出力例1

1
2

入力例2

7 11
1 2 2
1 3 1
2 4 2
2 5 2
2 6 1
3 4 1
3 5 1
3 6 1
4 7 2
5 7 2
6 7 1

出力例2

3
2
4
5