Constrained Mandatory Stop Shortest Path

You are given an undirected graph with n vertices and m edges. Each edge has a weight. In addition, there are k mandatory stops and g ordering constraints. The mandatory stops are exactly the vertices numbered from 2 to k+1. The g constraints are given as pairs \(r_i, s_i\); each means that if you stop at vertex \(s_i\) then you must have stopped at vertex \(r_i\) before (note that stopping is different from merely passing through a vertex).

Your task is to find the shortest path from vertex 1 to vertex n that stops at every mandatory vertex (i.e. vertices 2 to \(k+1\)) in an order that respects all given constraints. The path cost is the sum of the weights of the edges used. If no such path exists, output -1.

Notes:

• You are allowed to pass through any vertex even if it is not considered a stop.
• You may assume that the mandatory stops and the ordering constraints only involve vertices from 2 to \(k+1\).
• All edge weights are positive.

Below is the summary in mathematical notation:

• Graph has \(n\) vertices and \(m\) edges.
• Mandatory stops: vertices \(2, 3, \dots, k+1\).
• Ordering constraints: For each \(i=1,2,\dots, g\), a pair \((r_i, s_i)\) requires that the stop at \(r_i\) must occur before the stop at \(s_i\).
• Find the shortest path from vertex 1 to vertex \(n\) that stops at all mandatory vertices and obeys the constraints; output its cost, or -1 if it is impossible.

inputFormat

The first line contains four integers: n m k g.

The next m lines each contain three integers u v w representing an undirected edge between vertices u and v with weight w.

The next g lines each contain two integers r s representing an ordering constraint, meaning the path must stop at vertex r before it stops at vertex s.

Note: The mandatory stops are vertices 2 to k+1.

outputFormat

Output a single integer, the cost of the shortest valid path from vertex 1 to vertex n that stops at all mandatory vertices in an order obeying the constraints, or -1 if such a path does not exist.

sample

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

6

</p>