Problem E: Administrative Reform

 

Portugal The Portuguese government is studying a new administrative reform: every district will be split into only two municipalities, each one with its capital city. Besides, any community (town, village or hamlet) must belong to the municipality whose capital is closest to it, taking into account all existing roads. Communities whose shortest distances to both capitals are equal can choose their new municipality.

For instance, suppose that the capitals of the Lisbon district are the city of Lisbon and Arruda dos Vinhos. The city of Lisbon has to be in the Lisbon municipality. But how can people from Amadora know their new municipality? Although there are many routes from Amadora to Lisbon, the shortest one has 9.8 km (via Estrada de Monsanto), whereas the shortest route from Amadora to Arruda dos Vinhos has 38.3 km (taking the A9). Therefore, Amadora must belong to the new Lisbon municipality.

Task

Write a program that, given the communities (towns, villages and hamlets) of a district, the existing roads between them, and the two new capitals, X and Y, computes how many communities must belong to the X municipality, how many communities must belong to the Y municipality, and how many communities are allowed to choose (between X and Y). It is guaranteed that there is some route between any two communities of the district. Besides, different roads share at most one endpoint in common.

Input

The first line of the input has two integers: C, which is the number of communities, and R, which is the number of roads. Communities are identified by integers, ranging from 0 to C−1.

Each of the following R lines contains three integers, c1, c2 and l, which indicate that there is a (two-way) road between the distinct communities c1 and c2 whose length is l.

The last line has two different integers, X and Y, which are the communities chosen to be the new capitals.

Constraints

2 ≤ C ≤ 20 000Number of communities
1 ≤ R ≤ 150 000Number of roads
1 ≤ l ≤ 1 000Length of a road

Output

The output has a single line with three integers: the number of communities that must belong to the X municipality, the number of communities that must belong to the Y municipality, and the number of communities that can choose their new municipality.

Sample Input 1

4 5
1 2 20
0 1 30
2 0 12
1 3 1
0 3 30
2 1

Sample Output 1

2 2 0

Sample Input 2

8 14
6 5 75
5 7 20
6 2 21
2 7 75
6 0 40
0 2 26
0 1 15
0 3 18
1 3 7
1 2 12
4 1 25
5 4 5
7 4 37
2 4 38
1 7

Sample Output 2

5 2 1