빛 실험 장비 안에는 1부터 N까지 번호가 붙은 N개의 광학판이 있다.

일부 광학판 쌍은 광섬유 커넥터로 연결되어 있으며, 하나의 커넥터는 양쪽 방향으로 모두 신호를 보낼 수 있다.

커넥터를 통과할 때마다 정해진 양의 손실이 누적된다.

광선은 1번 광학판에서 들어와 N번 광학판에서 빠져나가야 한다.

그런데 실험을 성공시키려면 v1번 광학판과 v2번 광학판에서 각각 보정을 받아야 하므로, 두 광학판을 모두 통과해야 한다. 두 보정 지점을 통과하는 순서는 상관없다.

실험 장비의 구조상 같은 광학판이나 같은 커넥터를 여러 번 다시 사용할 수도 있다.

가능한 진행 방식 중 누적 손실이 가장 작은 값을 구하라. 조건을 만족하는 진행 방식이 없다면 -1을 출력한다.

입력

첫째 줄에 광학판의 개수 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번 광학판에서 N번 광학판까지 가면서 v1번 광학판과 v2번 광학판을 모두 통과할 때 가능한 누적 손실의 최솟값을 첫째 줄에 출력한다.

조건을 만족하는 진행 방식이 없으면 -1을 출력한다.

예제 입력 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