오리엔티어링 (Orienteering)

여러분이 다니는 JOI 고등학교에서는 해마다 한 번씩 전교생이 참가하는 오리엔티어링이 열린다. 오리엔티어링은 지도와 나침반을 사용해 산과 들에 설치된 체크포인트를 도는 경기이다.

JOI 고등학교의 오리엔티어링은 두 사람이 한 팀을 이뤄 참가한다는 특징이 있다. 각 팀의 두 사람은 지정된 출발 지점에서 함께 출발하지만, 그 뒤에는 따로 움직이며 지정된 도착 지점을 향한다. 두 사람이 도착 지점에 도달했을 때, 각 체크포인트는 팀의 두 사람 중 적어도 한 명이 방문해야 한다. 두 사람이 도중에 같은 지점을 방문해도 되고, 도중에 같은 길을 지나가도 된다.

JOI 고등학교의 오리엔티어링이 열리는 JOI 산에는 N개의 지점이 있고, 지점 사이를 M개의 길이 잇는다. N개의 지점에는 1부터 N까지 번호가 붙어 있다. 출발은 산기슭에 있는 지점 1이고, 도착은 산꼭대기에 있는 지점 N이다. 출발과 도착을 제외한 지점 가운데 일부 또는 전부가 체크포인트로 지정된다.

JOI 고등학교는 혼란을 피하기 위해 오리엔티어링이 진행되는 동안 각 길을 고도가 낮은 지점에서 고도가 높은 지점으로 가는 일방통행로로 만든다. 고도가 같은 두 지점은 없다. 출발인 지점 1은 고도가 가장 낮은 지점이고 도착인 지점 N은 고도가 가장 높은 지점이지만, 지점 번호가 반드시 고도가 낮은 지점부터 차례로 붙은 것은 아니라는 점에 주의하라. JOI 산에서는 이렇게 길을 일방통행로로 만들어도 지점 1에서 모든 지점으로 갈 수 있고, 모든 지점에서 지점 N으로 갈 수 있다.

조건을 만족하는 한 팀의 두 사람의 이동 방법에 대해 이동 거리 합의 최솟값을 구하는 프로그램을 작성하라. 그러한 두 사람의 이동 방법이 존재한다는 것은 보장된다.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 N, M이 공백을 구분으로 쓰여 있으며, 지점의 수가 N개, 길의 수가 M개임을 나타낸다.
• 이어지는 N개의 줄에는 각 지점이 체크포인트인지 여부가 쓰여 있다. 1+i번째 줄 (1 ≤ i ≤ N)에는 0 또는 1인 정수 Si가 쓰여 있으며, Si가 0이면 지점 i는 체크포인트가 아니고, Si가 1이면 지점 i는 체크포인트이다. 항상 S1 = SN = 0이다.
• 이어지는 M개의 줄에는 길의 정보가 쓰여 있다. 1 + N + j번째 줄 (1 ≤ j ≤ M)에는 정수 Aj, Bj, Cj가 공백을 구분으로 쓰여 있으며, 길 j는 지점 Aj에서 지점 Bj를 잇고, 길 j의 길이가 Cj임을 나타낸다. 지점 Aj는 지점 Bj보다 고도가 낮은 지점이고, 길 j는 지점 Aj에서 지점 Bj로 가는 일방통행로이다. 항상 Aj ≠ Bj이고, Aj = Ak이고 Bj = Bk인 길 k (k ≠ j)는 존재하지 않는다.

조건을 만족하는 한 팀의 두 사람의 이동 방법에 대한 이동 거리 합의 최솟값을 출력하라.

• 3 ≤ N ≤ 1 000, 지점의 개수
• 2 ≤ M ≤ 10 000, 길의 개수
• 1 ≤ K ≤ N − 2, 체크포인트의 수
• 1 ≤ Cj ≤ 10 000, 길 j의 길이

이 입력 예는 아래 그림에 대응한다. 체크포인트인 지점은 하늘색으로 표시되어 있다. 또한, 최소 이동 거리를 달성하는 두 사람의 이동 방법은 빨간색으로 표시되어 있다.