ペルーの Machu Picchu の新しいウォーターパークに着想を得て、Farmer John は牛のために作ろうと決めました。目玉は特別な設計の巨大スライダーです。

$E$ 本（$1 \le E \le 150,000$）の小スライダーが $V$ 個（$2 \le V \le 50,000$）のプール $1..V$ を結びます。各スライダーは正しい方向のみで逆行不可です。牛は 1 から次々に滑り、終点 $V$ に着きます。1 以外は少なくとも 1 本流入し、$V$ 以外は少なくとも別の 1 本が流出します。

どのプールからもスライダーを通り終点 $V$ に着けます。また、いったん出たプールへ何本か滑って再び戻ることはありません。

小スライダー $i$ は $P_{i}$ から $Q_{i}$（$1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$）で、楽しさ $F_{i}$（$0 \le F_{i} \le 2,000,000,000$）があります。Bessie の楽しさは通った全スライダーの値の和です。

長い列に並ぶので最大限楽しみたいです。通常は出口を注意して選びますが、牛なので高々 $K$ 回（$1 \le K \le 10$）制御を失い、ランダムな出口に滑ります。1 でも起こります。

最悪の場合の楽しさを最大化して選ぶと、どれだけ保証できますか？

3 プール（角括弧内は番号）、4 スライダーで $K$ が 1 の例です。括弧外は楽しさです。

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

常に 1 から 3 へ行きます。自由なら 1 から 2、次に楽しさ 5 の出口で 3 へ行き $5+5=10$。1 で制御を失うと直接 3 へ行って 9、2 で失うと $5+3 = 8$ に減るかもしれません。

$1\to3$ を選べば 9 です。1 で失って $1\to2$ へ行っても、2 ではもう失わないので 10 です。よって少なくとも 9 が保証されます。

入力

• 行 $1$：空白区切り整数 $V$、$E$、$K$。
• 行 $2..E + 1$：行 $i+1$ は空白区切り整数 $P_{i}$、$Q_{i}$、$F_{i}$。

出力

• 行 $1$：Bessie が保証できる最小の楽しさを表す整数 1 つ。

入出力例

入力 1

3 4 1
2 3 5
1 2 5
1 3 9
2 3 3

出力 1

9

問題作成者：John Pardon、2010