24162번 - 象使い (Route) 다국어

문제

あなたの友人の象使いは王宮まで象をつれて行くことを命ぜられた.道路図が与えられるが, 王宮までの道路はそれぞれ有料で,さらにその費用は自前で用意しなければならない.

彼のために最も安い道程を探し出して欲しい.

ただし,以下のことに注意すること.

• 道路は2つの料金所の間を結ぶ線分である.2つの料金所 p, q の組に対して,p と q を 結ぶ道路は高々1 本しか存在しない.
• 道路は必ず端点から端点までたどらなければならず,途中でほかの道路に乗り換えること はできない.
• 象は鋭角には曲れないため,料金所では,それまでたどった道路とのなす角が鋭角になる 道路には乗り換えられない. 例えば,下の図では,p → q → r はたどれず,u → v → w や x → y → z はたどれる.

입력

入力の 1 行目には,料金所の数 n (2 ≤ n ≤ 100) と道路の数 m が空白 で区切られて書かれている.i + 1 行目 (1 ≤ i ≤ n) には,2つの整数 x_i, y_i (−10000 ≤ x_i ≤ 10000, −10000 ≤ y_i ≤ 10000) が空白で区切られて書かれている.これは,i 番目の料金所の座 標が (x_i, y_i) であることを表わしている.j + n + 1 行目 (1 ≤ j ≤ m) には,3つの整数 a_j, b_j, c_j (1 ≤ a_j < b_j ≤ n, 0 ≤ c_j ≤ 10000) が空白で区切られて書かれている. これは,a_j 番目の料金 所と b_j 番目の料金所で結ばれる道路の通行料金が cj であることを表わしている.

現在の象の居場所は 1 番目の料金所である.王宮は 2 番目の料金所のすぐ近くにある.

출력

1 番目の料金所から 2 番目の料金所へ到達できる,最も安い料金を出力せよ.もし到 達不可能な場合は,−1 を出力せよ.

제한

힌트

入力例の図示

1 番目の料金所から 2 番目の料金所への道程は,1 → 2 と 1 → 4 → 2 の2つがあり,そのう ち料金が安い 1 → 4 → 2 の料金 8 を出力する.1 → 5 → 2 は,料金 2 だが,道路 1 ↔ 5 と道 路 5 ↔ 2 が 5 番目の料金所で鋭角をなすので,象は 1 → 5 → 2 とたどることはできない.