AT_joi2026final_f テレポーター 2 (Teleporter 2)

一本道に $ N $ 個の地点があり，左から順に $ 1, 2, \ldots, N $ の番号が付けられている．道は左から右への一方通行である． また， $ 1, 2, \ldots, M $ の番号が付いた $ M $ 個のテレポーター装置がある． 装置 $ i $ ( $ 1 \leqq i \leqq M $ ) を使用すると地点 $ S_i $ から地点 $ T_i $ ( $ S_i < T_i $ ) にワープ移動することができる． ビ太郎は現在地点 $ 1 $ におり，地点 $ N $ に向かおうとしている． ビ太郎が地点 $ j $ ( $ 1 \leqq j \leqq N-1 $ ) にいるときにとることができる行動は次のいずれかである． - 地点 $ j+1 $ に歩いて移動する． - $ S_i=j $ を満たす $ i $ ( $ 1 \leqq i \leqq M $ ) を選ぶ．装置 $ i $ を使用し，地点 $ T_i $ にワープ移動する． ワープ移動をすると体に負担がかかることが知られている． ビ太郎の体の安全について心配するあなたは，ビ太郎がどのような経路をとったとしてもワープ移動の回数が $ K $ 以下となるよう， $ 0 $ 個以上のテレポーター装置を破壊することにした． テレポーター装置 $ i $ はコスト $ C_i $ を支払うことで破壊することができ，その場合ビ太郎はその装置を使用することが不可能となる． ビ太郎がどのような経路をとったとしてもワープ移動の回数が $ K $ 以下となるように $ 0 $ 個以上のテレポーター装置を破壊するとき，支払うコストの総和としてありうる最小値を求めよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ K $ $ S_1 $ $ T_1 $ $ C_1 $ $ S_2 $ $ T_2 $ $ C_2 $ $ \vdots $ $ S_M $ $ T_M $ $ C_M $

標準出力に，支払うコストの総和としてありうる最小値を $ 1 $ 行で出力せよ． ---

### 小課題 1. ( $ 5 $ 点) $ K=1 $ ． 2. ( $ 3 $ 点) $ N\leqq 20 $ ， $ M\leqq 20 $ ． 3. ( $ 29 $ 点) $ N\leqq 500 $ ， $ M\leqq 500 $ ． 4. ( $ 23 $ 点) $ N\leqq 4\,000 $ ， $ M\leqq 4\,000 $ ． 5. ( $ 24 $ 点) $ N\leqq 40\,000 $ ， $ M\leqq 40\,000 $ ． 6. ( $ 16 $ 点) 追加の制約はない． --- ### Sample Explanation 1 装置 $ 3, 4 $ を破壊した場合を考える． ビ太郎が使用可能な装置は $ 1, 2 $ のみとなる．地点 $ 1 $ から地点 $ 8 $ に移動するときにビ太郎がワープ移動をする回数は必ず $ 1 $ 回以下となるため，条件を満たす． このとき，支払うコストの総和は $ 4 $ である． コストを $ 3 $ 以下にすることはできないので， $ 4 $ を出力する． この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 2 装置 $ 2, 5 $ を破壊するのが最適である． この入力例は小課題 $ 2,3,4,5,6 $ の制約を満たす． --- ### Sample Explanation 3 この場合，装置を破壊する必要はない． この入力例は小課題 $ 2,3,4,5,6 $ の制約を満たす． ### Constraints - $ 2 \leqq N \leqq 100\,000 $ ． - $ 1 \leqq K \leqq M \leqq 100\,000 $ ． - $ 1 \leqq S_i < T_i \leqq N $ ( $ 1 \leqq i \leqq M $ )． - $ 1 \leqq C_i \leqq 10^9 $ ( $ 1\leqq i \leqq M $ )． - 入力される値はすべて整数である．