Shortest Path Through a Required Node

You are given a directed graph G = (V, E) with n nodes and e edges. Each edge is represented by a triple \( (u, v, w) \), denoting an edge from node u to node v with a travel time (or weight) \( w \). Your task is to compute the shortest path from the start node \( s \) to the target node \( t \) such that the path passes through a specific node \( m \).

The problem can be formally defined as follows:

Find the minimum value of \( d(s, m) + d(m, t) \), where \( d(x, y) \) represents the shortest distance from node \( x \) to node \( y \). If either \( d(s, m) \) or \( d(m, t) \) is infinite (i.e. there is no path), output -1.

You are required to use Dijkstra's algorithm (or any other efficient shortest path algorithm) to solve this problem. The input is provided via standard input (stdin) and the result should be printed to standard output (stdout).

inputFormat

The first line of input contains five integers: n (number of nodes), e (number of edges), s (start node), t (target node), and m (required node to pass through).

This is followed by e lines, each containing three integers: u, v, and w, representing an edge from node u to node v with weight w.

All input is read from stdin.

outputFormat

Output a single integer: the total travel time of the shortest path from s to t that passes through node m. If no such path exists, output -1.

The output should be written to stdout.

## sample

5 7 0 4 2
0 1 10
0 2 3
1 2 1
1 3 2
2 3 8
2 4 5
3 4 2

8

</p>