코끼리 조련사 (Route)

당신의 친구인 코끼리 조련사는 코끼리를 왕궁까지 데려가라는 명을 받았다. 도로 지도가 주어지는데, 왕궁까지 가는 도로는 모두 유료이고 그 비용은 스스로 마련해야 한다.

그를 위해 가장 저렴한 경로를 찾아 주어야 한다.

단, 다음 사항에 주의한다.

• 도로는 두 요금소를 잇는 선분이다. 두 요금소 p, q의 쌍에 대해 p와 q를 잇는 도로는 많아야 1개만 존재한다.
• 도로는 반드시 끝점에서 끝점까지 따라가야 하며, 도중에 다른 도로로 갈아탈 수는 없다.
• 코끼리는 예각으로 굽을 수 없으므로, 요금소에서는 지금까지 따라온 도로와 이루는 각이 예각이 되는 도로로는 갈아탈 수 없다. 예를 들어, 아래 그림에서 p → q → r은 따라갈 수 없고, u → v → w와 x → y → z는 따라갈 수 있다.

입력의 첫째 줄에는 요금소의 수 n (2 ≤ n ≤ 100)과 도로의 수 m이 공백으로 구분되어 적혀 있다. i + 1번째 줄 (1 ≤ i ≤ n)에는 두 정수 xi, yi (−10000 ≤ xi ≤ 10000, −10000 ≤ yi ≤ 10000)가 공백으로 구분되어 적혀 있다. 이는 i번째 요금소의 좌표가 (xi, yi)임을 나타낸다. j + n + 1번째 줄 (1 ≤ j ≤ m)에는 세 정수 aj, bj, cj (1 ≤ aj < bj ≤ n, 0 ≤ cj ≤ 10000)가 공백으로 구분되어 적혀 있다. 이는 aj번째 요금소와 bj번째 요금소를 잇는 도로의 통행료가 cj임을 나타낸다.

현재 코끼리가 있는 곳은 1번째 요금소이다. 왕궁은 2번째 요금소 바로 근처에 있다.

1번째 요금소에서 2번째 요금소로 도달할 수 있는 가장 저렴한 요금을 출력하라. 도달할 수 없다면 −1을 출력하라.

입력 예의 그림

1번째 요금소에서 2번째 요금소로 가는 경로는 1 → 2와 1 → 4 → 2의 두 가지가 있고, 그중 요금이 저렴한 1 → 4 → 2의 요금 8을 출력한다. 1 → 5 → 2는 요금이 2이지만, 도로 1 ↔ 5와 도로 5 ↔ 2가 5번째 요금소에서 예각을 이루므로 코끼리는 1 → 5 → 2로 따라갈 수 없다.