301. Boring. Hot. Summer...

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

"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
to point
. 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
are junctions. The hijacker certainly chose one of the shortest routes from
. 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 A1 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 A2 different points of the village. The last suggestion came from N-th deputy chief, and you answered him with number AN. If the way of the criminal does not pass through the junction K for sure, AK will be equal to zero.

As you later noticed, the process of finding of A1, A2,..., AN 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, YN). 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 xi, yi, li — 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
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
1 2 1 1 4 2
1 3 1 2 4 1
3 4 1
1 3 3 1