Quiet Town

Time Limit : 3 sec, Memory Limit : 262144 KB

静かな町

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

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

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


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

Input

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

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

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

Output

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

Sample Input 1

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

Sample Output 1

1
2

Sample Input 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

Sample Output 2

3
2
4
5

Source: PC Koshien 2016 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2016-11-12
http://web-ext.u-aizu.ac.jp/pc-concours/