방향성이 없는 그래프가 주어진다.

\(1\)번 정점에서 \(N\)번 정점까지 이동하려고 한다. 이동하는 경로는 주어진 두 정점 \(v_1\)과 \(v_2\)를 모두 반드시 통과해야 한다. 두 정점을 통과하는 순서는 자유이며, 이미 이동했던 정점이나 간선을 다시 이용해도 된다.

조건을 만족하면서 \(1\)번 정점에서 \(N\)번 정점까지 이동하는 최단 거리를 구하시오.

입력

첫째 줄에 정점의 개수 \(N\)과 간선의 개수 \(E\)가 공백으로 구분되어 주어진다.

다음 \(E\)개의 줄에 세 정수 \(a\), \(b\), \(c\)가 공백으로 구분되어 주어진다. 이는 정점 \(a\)와 정점 \(b\)를 연결하는 거리가 \(c\)인 양방향 간선을 의미한다.

마지막 줄에 반드시 통과해야 하는 서로 다른 두 정점 \(v_1\)과 \(v_2\)가 공백으로 구분되어 주어진다.

출력

조건을 만족하는 최단 경로의 거리를 출력한다.

조건을 만족하는 경로가 없으면 -1을 출력한다.

제한 사항

• \(2 \le N \le 1,000\)
• \(0 \le E \le \min(200,000, N(N-1)/2)\)
• \(1 \le a, b \le N\)
• \(a \ne b\)
• \(1 \le c \le 1,000\)
• \(v_1 \ne v_2\), \(v_1 \ne N\), \(v_2 \ne 1\)
• 같은 두 정점을 연결하는 간선은 최대 하나만 주어진다.
• 답이 존재하는 경우 최단 거리는 \(2,147,483,647\) 이하이다.

예제 입력 1

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

예제 출력 1

7

예제 설명 1

\(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) 순서로 이동하면 두 정점 \(2\)와 \(3\)을 모두 통과한다. 이동 거리의 합은 \(3+3+1=7\)이다.