Festive Cake
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Petro, 53 years old, a confectioner, decided to bake a cake especially for the celebration of the 47th day of the year. Moreover, given the scale of the celebration of this significant event in Lviv, Petro plans to bake many cakes and connect some of them with waffle bridges. Rumor has it that there will also be several chocolate fountains in the composition.
According to the plan, there should be a total of \(n\) cakes connected by \(m\) bidirectional bridges. However, Petro has not yet finally decided what the lengths of the bridges will be: for some bridges he already knows the length, while for others he is still hesitating.
Petro believes that the celebration will be particularly successful if the shortest distance between cake number 1 and cake number \(n\) along the bridges is equal to \(w\). Help him determine the lengths of the bridges that would satisfy the desired condition. In case of success, Petro will treat you to his sweets.
Input
The first line contains three integers \(n\), \(m\), \(w\) — the number of cakes, the number of bridges, and the desired distance, respectively.
The next \(m\) lines each contain three integers \(u_i\), \(v_i\), \(w_i\). This means that the \(i\)-th bridge connects cakes with numbers \(u_i\) and \(v_i\) and has a length of \(w_i\). Moreover, if \(w_i = -1\), then the length of this bridge is not yet known.
It is guaranteed that there is a path along the bridges between any pair of cakes, and no bridge connects a cake to itself.
Output
Output \(m\) lines, one integer per line — the lengths of the bridges in the order they are given in the input data.
In case it is impossible to achieve the desired minimum distance,
output -1 in a single line.
Note that each bridge must have a positive integer length ranging from 1 to 200.
Constraints
\(1 \le n \le 100\),
\(1 \le u_i, v_i \le n\), \(u_i \neq v_i\),
\(1 \le m, w \le 200\),
\(w_i = -1\) or \(1 \le w_i \le 200\),
in 10 tests all bridges initially do not have a length.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 4 11 1 2 4 1 3 -1 2 4 -1 3 4 7 | 4 4 47 7 |
| Input (stdin) | Output (stdout) |
|---|---|
| 3 2 4 1 2 -1 2 3 4 | -1 |
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|