出题人:LZA
才华横溢的Poi同学会自己谱曲还能自己弹出来,有一天他想把自己的作品发到一个群里给大家康康,结果群主因为嫉妒把他禁言了...
于是他来到了20新生群。
Poi知道新生群里潜伏着很多学长,而且这些学长会把这些曲子转发到自己常去的群里,然后那个群里又有人会转发到其他群里...这样他的作品就可以一直被转发到目标群里面。Poi对每一个群里的学长构成了如指掌,所以他知道从u群到v群最多可以转发多少条曲子(学长们的品味都不一样,所以可以保证一个群里同一条曲子不会被同时转发到多个群里面)。
Poi的计划就是在20新生群(编号0)发他的作品集。现在Poi想知道这个计划能让多少条曲子被转发到目标群(编号n-1)。
输入共 m+1 行
第一行:两个整数 n , m .
接下来 m 行,每行三个整数 u , v , c ,代表从编号 u 的群到编号 v 的群最多可以转发 c 条曲子
一个整数,代表目标群可以收到的最大曲子数量
6 6 0 1 2 0 2 9 1 2 1 2 4 7 3 5 7 4 5 4
4
4 5 0 1 2 0 2 1 1 2 1 1 3 1 2 3 2
3
对所有测试点,都保证:对于任意群都可以向至少一个其他群转发(目标群不会有任何转发);一个群不会转发到自己。
数据范围:
2 \le n \le 100 , 0 \le u,v \le n , 1 \le c \le 10^8 .
另外为了简化编写难度,所有测试点保证中间计算不超过signed int32范围