[Usaco2010 Open]冲浪

题目描述

受到秘鲁的马丘比丘的新式水上乐园的启发，Farmer John决定也为奶牛们建 一个水上乐园。当然，它最大的亮点就是新奇巨大的水上冲浪。超级轨道包含 E (1 <= e="" <="150,000)条小轨道连接着V" (v="" 号水池。最后，由于这是一个冲浪，从任何一个水池出发都不可能回到这个水池)="" 每条小轨道从水池p_i到水池q_i="" (1="" 1<="Q_i" p_i="" !="Q_i)，" 轨道有一个开心值f_i="" (0="" 如果bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？="" 在样例中，考虑一个超级轨道，包含了3个水池(在图中用括号表示)和4条小轨道，k的值为1="" (开心值在括号外表示出来，用箭头标识)="" 她总是从1号水池出发，抵达3号水池。如果她总是可以自己选择，就是不会发生不能控制的情况她可以选择从1到2(这条轨道开心值为5)，再从2到3(开心值为5)，总的开心值为5+5=10。但是，如过她在1号水池失去控制，直接到了3，那么开心值为9，如果她在2号水池失去控制，她总的开心值为8。Bessie想要找到最大化开心值的方案，可以直接从1到3，这样，如果在1号水池失去控制，这样，她就不会在2号水池失去控制了，就能够得到10的开心值。因此，她的开心值至少为9

---

输入格式

* 第一行: 三个用空格隔开的整数: V, E, 和 K * 第2到第E+1行: 第i+1行包含三个用空格隔开的整数: P_i, Q_i, and F_i

---

输出格式

* 第一样: 一行一个整数表示在最坏情况下最大化的开心值

---

样例输入

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

---

样例输出

9

---

提示

没有写明提示

---

题目来源

Gold