acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem F

Evacuation Site

The council of your home city decided to build a public evacuation site to prepare for natural disasters. The evacuation site is desired to be built at a location reachable from as many locations across the city as possible, even when many road segments are closed due to a natural disaster. Given the road network of the city, please find the best candidate locations.

The road network is specified as an undirected graph. The nodes of the graph correspond to various locations in the city area, and the edges are two-way road segments connecting the locations. Each road segment is assigned a positive integer representing the assumed strength against disasters. A road segment with assumed strength s is expected to be available on a disaster of level below s, but will be closed on a disaster of level above or equal to s.

Adequacy of a location as an evacuation site is assessed by the following ordering. Let us define rs(v) as the number of locations that is directly or indirectly connected to the location v via road segments available even on the level-s disaster. We define the location u is more suitable than the location v as an evacuation site if and only if there exists some k ≥ 1 satisfying

  • r1(u) = r1(v),
  • r2(u) = r2(v),
  • ...
  • rk-1(u) = rk-1(v), and
  • rk(u) > rk(v).
Please find the best locations based on the above criterion. If two or more locations are rated equally as the best, enumerate all of them.

Input

The input consists of multiple datasets, each in the following format.

n m
a1 b1 s1
...
am bm sm

n is a positive integer less than or equal to 105, representing the number of locations. m is a non-negative integer less than or equal to 105, representing the number of road segments. The locations in the city are given ID numbers 1 through n. The i-th segment connects the locations ai and bi, and its assumed strength is si. Each of ai, bi, and si is an integer and they satisfy 1 ≤ ai < bin and 1 ≤ si ≤ 105. When ij, either aiaj or bibj holds. The given graph is connected. That is, there is at least one path between every pair of locations.

The end of the input is indicated by a line containing two zeros. The number of datasets does not exceed 50.

Output

For each dataset, output the list of the ID numbers of all of the locations most suitable with the criterion described above separated by a space character, in the increasing order, in a line.

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