Description

受到秘鲁马丘比丘新建水上乐园的启发，约翰农夫决定为奶牛们建造一个水上乐园。其最大的吸引力将是一个设计独特的巨型滑梯。超级滑梯由 $E(1 \le E\le150,000)$ 个迷你滑梯连接 $V(2\le V\le50,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)$。对于任何一次超级滑梯的滑行，贝茜的总乐趣是所有经过的迷你滑梯的乐趣值之和。

贝茜自然希望在滑梯排队等待的漫长时间里尽可能多地享受乐趣。通常，她会仔细选择从每个水池出来的迷你滑梯。然而，她是一头奶牛，在滑下滑梯的过程中最多有 $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$ 失去控制，她可能会直接从水池 $1$ 滑到水池 $3$，总乐趣为 $9$。如果她在水池 $2$ 失去控制，她的总乐趣可能会减少到 $5+3 = 8$。

贝茜希望找到她能获得的最大乐趣，因此她努力选择 $1\to3$，总乐趣为 $9$。如果她在水池 $1$ 失去控制而滑到迷你滑梯 $1\to2$，她知道她在水池 $2$ 不会失去控制，并且最终乐趣为 $10$。因此，她知道她的最小乐趣总是至少为 $9$。

Input Format

* 第 $1$ 行：三个用空格分隔的整数：$V$，$E$ 和 $K$。

* 第 $2$ 行到第 $E+1$ 行：第 $i+1$ 行包含三个用空格分隔的整数：$P_i$，$Q_i$ 和 $F_i$。

Output Format

* 第 $1$ 行：一个整数，表示贝茜可以保证获得的最小乐趣。

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

9 

Hint

（由 ChatGPT 4o 翻译）