#731. 收苹果

内存限制:512 MiB 时间限制:1000 ms 输入文件:apple.in 输出文件:apple.out
题目类型:传统 评测方式:文本比较
上传者: Payphone_X

题目描述

有一天,某人来到了苹果园,开始收苹果。

可是他发现他装的苹果太多了,导致袋子裂开了。他要从苹果园回到家里。

整个城市的道路网可以看作一个无向图,有 n 个节点, m 条道路,苹果园为 1 号点,他的家在 n 号点。

但他每走过一条路就会损失若干个苹果。请你计算出求出他到家最多还能剩多少个苹果 (注意:苹果为 0 时就不会再减少了)

输入格式

第一行三个整数 n m k 。分别代表节点数、道路数和初始的苹果数。

接下来 m 行,每行三个整数 u , v , w ,表示 u v 存在一条会损失 w 个苹果。

输出格式

一行一个整数,代表能够获得的最多苹果.

样例

样例输入

6 8 50
1 3 5
1 2 6
1 5 7
1 6 10
3 5 9
3 4 1
4 6 3
2 5 5

样例输出

41

数据范围与提示

对于 30\% 的数据,满足 0 < n < m \leq 10 0 < w \leq 10^9

对于另外 30\% 的数据,满足 0 < n \leq 1000,m = \frac{n * (n - 1)}{2},0< w \leq 10^9

对于 100\% 的数据,满足 0 < n \leq 10^5 , 0< w \leq 10^9