A directed weighted acyclic graph is given. It is required to find the shortest path in it
from vertex s to vertex t.
Input:
The first line of the input file contains four integers n, m, s and t - the number of vertices, edges of the graph, the initial and final vertices, respectively (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
The next m lines contain the descriptions of the edges, one per line.
Edge number i is described by three integers b
i, e
i and w
i - the beginning, end and length of the edge, respectively (1 <= b
i, e
i <= n;|w
i| <= 1000).
The graph does not contain cycles and loops.
Output:
The first line of the output file must contain a single integer - the length of the shortest path from s to t.
If there is no path from s to t, print "Unreachable".
Examples:
| Input |
Output |
2 1 1 2
1 2 -10
| -10 |
2 1 2 1
1 2 -10
| Unreachable |