时间限制：1秒　　内存限制：256M

---

【题目描述】

　　神秘的太空逐渐成为人类的乐园，人们建立了 \(m\) 条太空轨道，这些轨道连接着 \(n\) 个星球，星球编号为 \(1..n\)。

　　每条太空轨道必须按照特定的方向运行，不能够反向运行。人们从 1 号星球出发，经过若干条太空轨道，最终到达 \(n\) 号星球。除了 \(n\) 号和 1 号之外的每个星球，都至少有一条太空轨道进来和一条太空轨道出去，并且，人们从任何一个星球都能到达 \(n\) 号星球。由于太空轨道是单向的，所以人从任何一个星球出发后，他就不能通过太空轨道回到这个星球了。

　　每条太空轨道从星球 \(u_i\) 到星球 \(v_i (1 ≤ u_i,v_i ≤ n; u_i≠v_i)\)， 轨道上有一个开心值 \(f_i\) ，总的开心值就是经过的所有轨道的开心值之和。人们自然希望越开心越好。因此，总是要精心地挑选路线。但是，由于人类有时候也要犯错，所以，在选择路线时并不总是选择最开心的路线前进，而会从某个星球随机选择了一条轨道到另一个星球（这种情况甚至会在1号星球发生），但犯错的情况至多只会出现 \(k\) 次。

　　现在需要计算一下，在最坏情况下（即在最多犯 \(k\) 次错的情况下），从 1 到 \(n\) 的最大开心值是多少？

【输入格式】

　　第一行包含三个用空格隔开的整数: \(n,m\) 和 \(k\)。
　　接下来的 \(m\) 行，第 \(i+1\) 行包含三个用空格隔开的整数: \(u_i, v_i\) 和 \(f_i\)。

【输出格式】

　　一行一个整数表示在最坏情况下最大化的开心值。

【输入输出样例】

　Input

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

　Output

9

【样例解释】

　　在样例中，包含了 3 个星球和 4 条太空轨道，\(k\) 的值为 1。人们是从 1 号星球出发，抵达 3 号星球。如果可以自己选择，就是不犯错的情况，人们可以选择从 1 到 2(这条轨道开心值为 5 )，再从 2 到 3(开心值为 5 )，总的开心值为 5+5=10。

　　但是，如过她在 1 号星球犯错，直接到了 3，那么开心值为 9 ，如果她在 2 号星球犯错，她总的开心值为 8。想要找到最大化开心值的方案，可以直接从 1 到 3，这样，如果在 1 号星球犯错，她就不会在 2 号星球犯错，就能够得到 10 的开心值。因此，她的开心值至少为 9。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤50000\)，\(1≤m≤150000\)，\(1≤k≤10\)，\(1≤f_i≤10^9\)。

【来源】

　　Mr.he