受秘鲁 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