007 - 静かな町

問題

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

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

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

課題

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

入力

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

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

時間制限

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

出力

与えられた道の情報に対して、駅伝大会のコースになることがない町をすべて出力する。１行目に駅伝大会のコースになることがない町の数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