Shortest Path Avoiding a Damaged Node

You are given a directed weighted graph with (n) nodes and (m) edges. Each edge has a weight (w). Additionally, there is a damaged node (d) that must not be visited in the path. Your task is to compute the shortest path from a starting node (s) to a target node (t) that does not pass through the damaged node (d). If no valid path exists, output (-1).

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line contains five integers (n), (m), (d), (s), and (t) — the number of nodes, the number of edges, the index of the damaged node, the starting node, and the target node respectively. The following (m) lines each contain three integers (u), (v), and (w), representing a directed edge from node (u) to node (v) with weight (w).

outputFormat

Output a single integer: the length of the shortest path from (s) to (t) that does not pass through the damaged node (d), or (-1) if such a path does not exist.## sample

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

17