// problem #84

특정한 최단 경로

양방향 그래프에서 1번에서 N번으로 가되, 반드시 정점 v1과 v2를 모두 지나는 최단 경로 길이를 구하시오. 불가능하면 -1.

입력

첫 줄 정점 수 N, 간선 수 E. 이후 E개 줄에 a b c. 마지막 줄에 v1 v2.

출력

조건을 만족하는 최단 경로 길이(불가능 -1).

제한

• 2 ≤ N ≤ 800
• 1 ≤ E ≤ 200,000
• 1 ≤ c ≤ 1,000

예제

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

7