《 图 论 》

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

4 6 3 13
13 7 1
13 11 2
13 3 3
11 3 4
7 11 5
7 3 6

样例输出

8