オリエンテーリング (Orienteering)

あなたの通う JOI 高校では，年に一度，オリエンテーリングが行われ，全校生徒が参加する．オリエン テーリングとは，地図と方位磁針を用い，山野に設置されたチェックポイントを巡る競技である．

JOI 高校のオリエンテーリングは，2 人一組のチームで参加するという特徴がある．各チームの 2 人は， 指定されたスタート地点から一緒にスタートするが，その後は別々に行動をし，指定されたゴール地点を 目指す．2 人がゴール地点に到達した際，それぞれのチェックポイントをチームのうちの少なくとも 1 人 が訪れていないとならない．2 人は途中で同じ地点を訪れても構わない．また，2 人が途中で同じ道を通っ ても構わない．

JOI 高校のオリエンテーリングが行われる JOI 山には，N 個の地点があり，それらの間を M 本の道が 繋いでいる．N 個の地点には 1 から N までの番号が付いている．スタートはふもとにある地点 1 であり， ゴールは頂上の地点 N である．スタートとゴール以外の地点のうち一部または全部がチェックポイントと して指定される．

JOI 高校は，混乱を避けるため，オリエンテーリングの間，それぞれの道を，高度が低い方の地点から 高度が高い方の地点への一方通行とする．高度が等しい 2 つの地点は存在しない．スタートである地点 1 は最も高度の低い地点であり，ゴールである地点 N は最も高度の高い地点であるが，地点の番号は必ずし も高度の低い地点から順につけられているわけではないことに注意せよ．JOI 山では，このように道を一 方通行にしても，地点 1 から全ての地点に行くことができ，また，全ての地点から地点 N に行くことがで きる．

条件を満たすような一組のチームの 2 人の移動方法に関して，移動距離の合計の最小値を求めるプログ ラムを作成せよ．そのような 2 人の移動方法が存在することは保証されている．

標準入力から以下の入力を読み込め．

• 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) は存在しない．

条件を満たすような一組のチームの 2 人の移動方法に関する，移動距離の合計の最小値を出力せよ．

• 3 ≤ N ≤ 1 000 地点の個数
• 2 ≤ M ≤ 10 000 道の本数
• 1 ≤ K ≤ N − 2 チェックポイントの数
• 1 ≤ Cj ≤ 10 000 道 j の長さ

この入力例は，下図に対応する．チェックポイントとなっている地点は水色で示されている．また，最 小の移動距離を達成する 2 人の移動方法は赤色で示されている．