说明

在日常生活中有大量的网络，如电网、水管网、交通运输网、通信网及生产管理网等，网络流正是从这些实际问题中提炼出来的，目的是求网络最大流。

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入结点个数n和边数m（1<=n<=50，1<=m<=2500）。

接下来m行，输入结点u，v及边（u--v）的容量w（1<=u,v<=50，1<=w<=100）。

输出格式

对于每一组输入，输出网络的最大流值。

每组的输出占一行。

样例

2
6 9
1 2 12
1 3 10
2 4 8
3 2 2
3 5 13
4 3 5
4 6 18
5 4 6
5 6 4
4 5
1 2 3
1 3 5
2 4 5
3 2 3
3 4 2

18
7

来源

《趣学算法》7.3节