受秘魯 Machu Picchu 新水上樂園啟發，Farmer John 決定為乳牛建一個樂園。最大亮點是一座設計獨特的巨大水滑梯。

巨大滑梯由 $E$ 條小滑梯（$1 \le E \le 150,000$）連接 $V$ 個水池（$2 \le V \le 50,000$），編號 $1..V$。每條只能沿正確方向，不能逆行。乳牛從池 1 出發，連續滑行直到終點池 $V$。每池除 1 外至少一條滑梯進入，除 $V$ 外至少另一條離開。

從任意池均可沿一些滑梯到達終點 $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 一趟總樂趣為所經滑梯樂趣值之和。

排隊等了很久，Bessie 自然想盡興。牠通常仔細選擇出口，但畢竟是乳牛，一趟至多 $K$ 次（$1 \le K \le 10$）失去控制，隨機沿一個出口滑走，甚至可在池 1 發生。

若選擇使最壞情況樂趣最大，能保證多少樂趣？

例如 3 個池（方括號為編號）、四條小滑梯，$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

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

輸出格式 1

9

題目作者：John Pardon，2010