Ensure No Absence

In the year 2022, the scu acmers decide to hold a party, and most of the old scu acmers have recieved the invitation, including onmylove, tanlinghang, and zsasuke (the original members of the scu isap team).
As they graduated from scu ten years ago, they live in dierent cities currently. They are all very arrogant, and each believes himself to be the best runner among all the scu acmers. To prove this, they all decide to spend days running to the destination (the city where the party is to be held), and to save energy, they each will choose the shortest route for himself(there may exist more than one shortest routes, in such cases, they would choose one of them at random). But this lead to a series of problems: they may stop to rest occasionally, and once they meet each other on one same road, they will stop running and begin to argue for days who is the best runner, entirely forgetting the party.
The scu leaders are all very considerate, they don't want the absence of anyone, so they will select a suitable city to hold the party to guarantee that the isap team members will not meet each other on their way to the party. But they are all very busy, so the task is assigned to you, brilliant icpcer!

Process till EOF.
Each case contains two positive integers n,m(3 ≤ n ≤ 3000; 1 ≤ m ≤ 200000) in the first line. Indicating the number of cities to choose from, and the number of the edges (onmylove lives in city 1, tanlinghang lives in city 2, and zsasuke, city 3), then m lines follow, each line contains 3 positive integers a, b, c (1 ≤ a, b ≤ n; 1 ≤ c ≤ 10; b ≠a, there is at most one edege between two distinct cities) indicating that it takes each of them(onmylove, tanlinghang, or zasuke) c days to get to city b from city a, or c days to get to city a from city b if running at full speed(from this, you know they all run at the same speed, so there is no point in arguing at all,but they are all very unreasonable!)

For each case, if there are no cities satisfying the conditions above, you should puts "impossible" in a single line,otherwise, you should print a number n(the number of cities satisfying the conditions) in a line, the second line contains n integers, meaning the ids of the cities satisfying the conditions, and besides,sort them in increasing order.

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

1
2
1
4
1
5

In the first case, we could not choose city 3 to hold the party, since tanlinghang may rest on the road between 2 and 3, so onmylove may meet tanlinghang on the same road
and fall into arguing. so we choose city 2 to hold the party.In the third case, we could not choose city 4 for the same reason. suppose we choose city 4, the shortest route for
onmylove is 1-5-4, and the shortest route for tanlinghang is 2-5-4 or 2-4, if tanlinghang choose the route 2-5-4, he may meet onmylove on the road between 5 and 4,
and arguing is inevitable.

zsasuke

2010 Asia Regional Chengdu Site —— Online Contest