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 $ )．
• 入力される値はすべて整数である．