Problem D. Document signing

Author:A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You have a document that needs to be signed by university president. It's hard to get president's time, but luckily you know his current location in the university campus. You also know that he is heading to his office now, so you can try to intercept him on the way and ask for a signature. Even more, everyone at university knows that president always takes fastest path wherever he goes. However, if there are several fastest paths, the president chooses any of them.

You need to write a program that determines whether you can guarantee meeting the president no matter which of the fastest path he picks, if you start moving from your room at the same time as the president.

More formally, university campus map is given as an undirected graph. i-th edge is given by its vertices (ai, bi) and traversal time ti (this is a traversal time for any human, either you or the president). Initially, the president is located at vertex p1 and is taking one of the fastest paths to his office located at vertex f. You are initially located at vertex p2. You can get the signature if you meet the president at vertex v such that:

Input file format

Input file starts with two integers: n — the number of vertices and m — the number of edges.

Then m edges are given by integers ai, bi, ti. Vertices are numbered starting from 0.

Finally, there are three integers f, p1, and p2.

Output file format

Output file must contain the number of vertices where it is possible to get the signature, followed by the list of vertex numbers in ascending order.

Constraints

It is guaranteed that the graph is connected, i.e. it's possible to get from any vertex to any other vertex.

There is no more than one edge between each pair of vertices (ai, bi).

2 ≤ n ≤ 1000, 1 ≤ m ≤ n(n − 1) / 2

0 ≤ ai, bi, p1, p2, f < n

ai ≠ bi, p1 ≠ p2

0 < ti ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
8 9

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

3
0
5
4
1 3 4 7
2
8 9

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

3
0
5
0

0.092s 0.013s 13