Description

给定一个有向带权图，找出最大流。

Format

Input

输入的第$1$行包含一个整数$T$，表示测试用例的数量。每个 测试用例的第$1$行都包含两个整数$N$ 和$M$ $（2≤N ≤15，0≤M≤1000）$，表示节点和边的数量。接下来的M 行，每行都包含三个整 数$X$ 、$Y$ 和$C$ ，表示从$X$ 到$Y$ 有一条边，其容量为$C$$（1≤X ，Y ≤N，1≤C ≤1000）$。

Output

对每个测试用例，都输出从源$1$到汇$N$ 的最大流。

Samples

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Case 1：1
Case 2：2