"Hello, dear Dima Malikov.

If you still do not know me,

My name is Ignat..."

From the letter of Ignat (the biggest fan) to Dima Malikov.

You are the head of the ROVD of the village Big Valenki. Recently you got a message informing that some stranger hijacked a tractor and currenly is making his way from point

X

to point

Y

. The roads in the village are bidirectional and connect the pairs of junctions. Village has N junctions and M roads. Each road has some fixed length. Points

X

and

Y

are junctions. The hijacker certainly chose one of the shortest routes from

X

to

Y

. Your first deputy chief suggested that the criminal should be intercepted on the junction number 1, but you noticed that at the moment when the criminal could reach this junction he can actually be at one of A₁ different points of the village (some of these points could be at the roads). Your second deputy chief suggested that interception should be arranged at the second junction. But you noticed again that at that time criminal could be at A₂ different points of the village. The last suggestion came from N-th deputy chief, and you answered him with number A_N. If the way of the criminal does not pass through the junction K for sure, A_K will be equal to zero.

As you later noticed, the process of finding of A₁, A₂,..., A_N sequence can be automated. You are to write a program which will find this sequence.

The first line of the input contains three natural numbers N, X, Y (1≤ N≤ 2000; 1≤ X, Y≤ N). The second line contains the only number M (0≤ M≤ 200000). The following lines contains the description of roads. Each description is three integer numbers x_i, y_i, l_i — the pair of junctions it connects and its length. The lengths of all roads are integer numbers from 1 to 10000. Between each pair of junctions there is no more than one road. The road cannot connect junction to itself.

Output the desired sequence.

sample input	sample output
6 2 5 9 1 2 1 1 3 10 1 6 1 4 6 1 6 5 1 2 6 2 3 6 1 5 3 1 4 5 1	2 1 0 0 1 1

sample input	sample output
4 1 4 5 1 2 1 1 4 2 1 3 1 2 4 1 3 4 1	1 3 3 1