缓解运输压力

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

为了缓解A市到B市的运输压力,政府决定重修一些村镇之间的主要交通干道。这个时候,不少承包商蠢蠢欲动。因为每修一条路,都能获得大量利润。
 为了过滤掉一批无脑的承包商,政府提出,重修的道路必须要做到,如果修这一条就能提高A市到B市整个的交通运输量,才支付给承包商钱,否则一切费用由承包商自理。不但如此,因为修路会给道路所连的两个村镇带来不便,所以承包商必须给道路两边的村镇支付一定补偿金。(对于每个村镇,补偿金只发一次)。
 承包商L知道你是搞ACM的,这个对你来说一定不是难题,所以想要你帮他挑选一些道路来修以获得最大利润。

Input

第一行,N,M,P,L. N表示A市到B市可能经过的N个村镇,其中1表示A市,运输起点,N表示B市,运输终点。 M表示整个运输网络有M条有向公路。 P代表修建道路要给道路关联的每个村镇补偿金。 L是如果一条路修建成功,能获得的利润。 下面M行,每行三个参数a,b,c,代表一条有向的道路连接的村镇编号a和b,和由a村镇运至b村镇的现有运输量c。(保证没有重边,但存在b,a,c’,表示由b到a的运输量c’) 数据范围: 0<N<1000;0<M<1000000;0<P<L<100;0<c<100

Output

能获得的最大利润S。

Sample Input

4 4 2 10
1 2 3
1 3 2 
2 4 1
3 4 4

6 7 1 3
1 2 10
2 3 4
3 4 2
3 5 1
2 4 1
4 5 5
5 6 10

Sample Output

12
5

Hint

Source

The First ACM-ICPC Nanjing Invitational Tourn

提交代码