Shortest Path in a Directed Graph

You are given a directed graph with ( n ) nodes and ( m ) edges. Each edge is described by three integers ( u ), ( v ), and ( w ), denoting a directed edge from node ( u ) to node ( v ) with weight ( w ). Your task is to compute the shortest path from a given start node to a target node using Dijkstra's algorithm.

The input is provided via stdin and the output should be printed to stdout. If there is no path from the start node to the target node, output -1.

The key recurrence in the algorithm is given as: ( d[v] = \min(d[v],\ d[u] + w) ) for every edge ( (u, v, w) ).

inputFormat

The first line contains two integers ( n ) (number of nodes) and ( m ) (number of edges). Each of the following ( m ) lines contains three integers ( u ), ( v ), and ( w ), indicating a directed edge from node ( u ) to node ( v ) with weight ( w ). The last line contains two integers representing the start and target nodes.

outputFormat

Output a single integer which is the length of the shortest path from the start node to the target node. If the target node is unreachable, output -1.## sample

4 6
1 2 4
1 3 2
3 2 1
2 4 7
3 4 3
2 3 2
1 4

5