Shortest Path Through Required Vertices

An undirected weighted graph is given. Find the minimum distance from vertex 1 to vertex N among all paths that visit both of two specified distinct vertices v1 and v2.

Vertices and edges may be visited more than once. Only the total distance must be minimal among paths satisfying the requirement.

The first line contains the number of vertices N and the number of edges E. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)

Each of the next E lines contains three integers a, b, and c, meaning that there is an undirected edge of distance c between vertices a and b. (1 ≤ c ≤ 1,000)

The last line contains the two distinct vertices v1 and v2 that must both be visited. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

There is at most one edge between any pair of vertices.

Print the length of the shortest path from vertex 1 to vertex N that visits both required vertices. If no such path exists, print -1.