A relay network has n nodes (numbered 0 to n-1) joined by one-way links, each taking a positive integer number of ticks to carry a signal from its start node to its end node.
At tick 0, TWO beacons at nodes a and b broadcast simultaneously. A node receives the signal at the earliest tick any copy (from either beacon, along any path) reaches it; nodes a and b themselves are received at tick 0. Report the tick at which the last node is covered — the maximum over all nodes of the earliest arrival time. If some node is never reached from either beacon, report that the network is not fully covered.
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way link from u to v taking w ticks.
Final line: two integers a b, the two broadcasting nodes.
Output format
A single integer: the tick when every node has been covered, or -1 if some node is never reached.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= a, b, u, v <= n-1 (a and b may be equal)
- 1 <= w <= 1000000