A communications backbone has n routers (numbered 0 to n-1) linked by one-way channels, each with a positive integer cost. Consider all routes (directed paths) from router s to router t.
First minimize the total cost of the route. Among all routes achieving that minimum cost, minimize the number of edges (hops) used. Report the minimum cost together with that fewest hop count. If t is unreachable from s, report that it is impossible. If s equals t, the answer is cost 0 with 0 hops.
Because all costs are positive, a minimum-cost route never repeats a router, so both the cost and the tie-breaking hop count are well defined.
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a one-way channel from u to v with cost w.
Final line: two integers s t.
Output format
If t is reachable, print two space-separated integers: the minimum cost and the fewest number of hops among minimum-cost routes. Otherwise print -1.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= s, t, u, v <= n-1
- 1 <= w <= 1000000