Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

The first line of input contains an integer $T$, denoting the number of test cases.
For each test case, the first line contains two integers $N,M\ (2 \leq N \leq 15,\ 0 \leq M \leq 1,000)$, denoting the number of vertexes and edges in the graph.
Next $M$ lines, each line contains three integers $X, Y,C\ (1 \leq X,Y \leq N,\ 1 \leq C \leq 1,000)$, there is an edge from $X$ to $Y$ and the capacity of it is $C$.

For each test cases, you should output the maximum flow from source $1$ to sink $N$.