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

---

【问题描述】

　　沿着航空旅行的路线上有 \(N\) 个由编号为 1 到 \(N\) 的机场。每个机场都有 \(M\) 个旅客想要乘坐飞机旅行。每一旅客想要从一个机场飞往另一个机场，航班可以在某些机场停下来带上部分或全体旅客。旅客们登机后会一直停留直至到达目的地。

　　航空公司可以安排飞机每天清晨，从 1 号机场飞往 N 号，晚上再 N 号机场飞回 1 号。在某些机场，他们需要你帮助来决定每天携带那些旅客。

　　提供给你飞机的容量为 \(C\)，同时提供给你想要旅行的旅客信息，请你计算出这一天的航班最多能满足多少旅客的愿望。

【输入格式】

　　第 1 行有 3 个整数：\(K,N,C\)。
　　接下来的 \(K\) 行，每行包含 3 个整数: \(S,E,M\) ，表示有 \(M\) 个旅客想从机场 \(S\) 乘飞机到机场 \(E\)。

【输出格式】

　　以完成旅行的旅客人数的最大值。

【输入输出样例】

　Input

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

　Output

6

【数据限制】

　　对于 \(100\%\) 的数据满足：\(1<=N<=10000\)，\(1<=K<=50000\)，\(1<=C<=100\)

【来源】

　 Mr.he