Reassign Communication Costs

You are given a directed graph with (n) vertices and (m) edges. Each edge has an associated communication cost. Some edges have their cost disturbed (recorded as 0) and need to be replaced with a positive integer. Your task is to determine whether it is possible to assign a positive integer to each disturbed edge so that the communication cost (i.e. the weight of the shortest path) from a given source vertex (s) to a target vertex (t) is exactly (C). If a valid assignment exists, output “POSSIBLE” followed by the new cost for each edge in the input order (for an edge whose original cost is nonzero, output its unchanged cost; for an edge with disturbed cost, output your assigned value). Otherwise, output “IMPOSSIBLE”.


Formally, let the edges be given as ((u_i, v_i, c_i)) for (i=1,2,\dots,m) where (c_i) is either a positive integer (fixed) or 0 (disturbed). Find an assignment of a positive integer to every disturbed edge such that if (d(s,t)) is the minimum cost from (s) to (t) in the resulting graph, then (d(s,t) = C).

If multiple answers exist, any one is accepted.

inputFormat

The input is read from standard input. The first line contains five integers (n), (m), (C), (s), and (t) (with 0-based indexing for vertices). It is followed by (m) lines; each line contains three integers (u), (v), and (c) representing an edge from vertex (u) to vertex (v) with communication cost (c). A cost of 0 indicates that this edge is disturbed and needs to be assigned a positive integer.

outputFormat

Print to standard output. If a valid assignment exists, print "POSSIBLE" on the first line, followed by (m) lines. The (i)-th following line should contain three integers (u), (v), and (w), where (w) is the assigned (or original, if nonzero) cost of the corresponding edge in the input order. If no valid assignment exists, output just "IMPOSSIBLE".## sample

4 4 10 0 3
0 1 5
1 2 0
2 3 2
0 3 0

POSSIBLE
0 1 5
1 2 3
2 3 2
0 3 4