描述

在Z国和W国之间一直战火不断。
好不容易,W国的间谍把完整的Z国的军事基地的地图到手了。
于是W国决定再次出击,一举击破Z国的防线。
W国认真研究了Z国的地形,发现Z国有N个军事基地,我们不妨编号成1..N,而且经过深刻研究,发现1号军事基地是资源补给基地,而N号军事基地是前线。
由于地形的缘故,只有M对军事基地两两可达,当然是有距离的。
此时W国的弹头紧缺,当下的弹头只能去毁灭一个军事基地。当然了,最重要的就是毁灭一个军事基地,使得资源补给基地与前线的最短距离发生变化。但是Z国也不是白痴,他们的资源补给基地与前线有着极高的防御力,所以W国只能去炸掉其余的N-2个基地,当然炸掉某个基地后,这个基地就不可达了。
于是问题就来了,炸掉哪些基地后会使得资源补给基地与前线的最短距离发生变化呢?
注:假若炸掉某个基地后,1号基地和N号基地不连通,那么我们也认为他们的最短距离发生了变化。

输入格式

输入数据第一行是两个正整数N,M,意义如题所述。
接下来M行,每行包括三个正整数x,y,d,表示有一条边连接x、y两个地点,其距离为d。
数据保证图是连通的。

输出格式

输出数据的第一行包含一个整数K,表示有K个基地可毁灭,且毁灭其中任意一个后,资源补给基地与前线的最短距离发生变化。
接下来K行,每行输出一个军事基地的编号,要求编号递增。
在wyl8899神犇的率领下,W国必胜!!! 
因此一定不会存在K=0的情况。

样例输入

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

样例输出

1
2

数据范围与约定

对于30%的数据,N<=100,M<=1,000;
对于60%的数据,N<=2,000,M<=20,000;
对于100%的数据,N<=10,000,M<=100,000,1<=d<=10,000;