필수 정점을 지나는 최단 경로

방향이 없는 가중 그래프가 주어진다. 1번 정점에서 N번 정점으로 이동할 때, 서로 다른 두 정점 v1과 v2를 모두 반드시 지나는 경로 중 거리의 합이 가장 작은 경로를 구하라.

정점과 간선은 여러 번 지나도 된다. 단, 조건을 만족하는 경로 중 전체 이동 거리는 최소여야 한다.

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)

다음 E개의 줄에는 세 정수 a, b, c가 주어진다. 이는 a번 정점과 b번 정점 사이에 거리 c인 양방향 간선이 있음을 뜻한다. (1 ≤ c ≤ 1,000)

마지막 줄에는 반드시 지나야 하는 서로 다른 두 정점 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

임의의 두 정점 사이에 존재하는 간선은 최대 1개이다.

두 필수 정점을 모두 지나 1번 정점에서 N번 정점으로 가는 최단 경로의 길이를 출력한다. 그런 경로가 없으면 -1을 출력한다.