Lucky Path Road Closure

You are given a country with n towns (numbered from 1 to n) and m bidirectional roads. Town Bit is located at town a and town Hex at town b. Each road has a length. Since you know the map very well, you have precomputed a shortest path from town a to town b and decided to call this path the lucky path (i.e. the lucky path is such that its total length is minimized, formally, its length is the distance d(a,b) computed by Dijkstra's algorithm).

One day the government starts construction on the roads. To keep traffic flowing, exactly one road is closed at a time (when closed, the road is not available for travel). For each road (edge) in the lucky path, determine the shortest distance between town Bit and town Hex when that particular road is closed. If there is no alternative route when a road is closed, print -1 for that case.

Note: All formulas must be expressed in LaTeX format (for example, $n$, $m$, $a$, $b$, $d(a,b)$).

inputFormat

The first line contains four integers $n$, $m$, $a$, and $b$, where $n$ is the number of towns, $m$ is the number of roads, and $a$ and $b$ denote the town numbers for Bit and Hex respectively.

Each of the next $m$ lines contains three integers $u$, $v$, and $w$, indicating that there is a bidirectional road between towns $u$ and $v$ with length $w$.

outputFormat

Output $r$ integers separated by spaces, where $r$ is the number of roads in the lucky path. The $i$-th integer represents the shortest distance from town $a$ to town $b$ when the $i$-th road (in order along the lucky path) is closed. If there is no valid path, output -1 for that case.

sample

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

4 4