Tour De Chittagong

The city of Chittagong can be considered a weighted directed acyclic graph (DAG) of $n$ nodes and $m$ edges. There are $k$ friends who want to visit the city. But visiting all the nodes for each friend can be too much of a hassle. So, we consider a node is visited when at least one of the friends visited it.

The friends can start from any node they want. That is, any friend can start in any node and multiple friends can also start in a single node too.

Now, they will start moving. At each moment,

• A friend can move from node $u$ to $v$ if, the friend is currently in node $u$ and there is an edge from $u$ to $v$. The cost of this operation is the weight of the edge $u \rightarrow v$.

• A friend can stay in his current node. The cost of this operation is $0$.

The total cost is the sum of cost of all operations. Help the friends to find the minimum total cost to visit all the nodes or output $-1$, if it is impossible to visit all the nodes by $k$ friends.

Input

The first line of the input contains a single integer $t (1 \le t \le 10)$ — the number of test cases.

The first line of each test case contains three integers $n,m$ and $k$ $(1 \le n \le 100, 0 \le m \le 300, 1 \le k \le n)$ — the number of nodes, the number of edges and the number of friends.

The following $m$ lines describe the edges. Each contains three integers $u, v, w$ $(1 \le u,v \le n, u \ne v, 1 \le w \le 10^6)$ — the directed edge $u \rightarrow v$ and the weight of the edge.

It is guaranteed that, the given graph is directed acyclic and there are no multiple edges.

Output

For each test case, if it is impossible to visit all the nodes output $-1$. Otherwise, output the minimum total cost to visit all the nodes.

Samples

Input	Output
3 6 5 2 1 3 3 2 3 2 3 4 5 4 5 4 4 6 7 6 5 3 1 3 3 2 3 2 3 4 5 4 5 4 4 6 7 6 5 1 1 3 3 2 3 2 3 4 5 4 5 4 4 6 7	26 11 -1
Test case $1$: The following can be the optimal paths. Friend $1$: $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$, Cost: $3+5+4 = 12$. Friend $2$: $2 \rightarrow 3 \rightarrow 4 \rightarrow 6$, Cost: $2+5+7 = 14$. All the nodes are visited. Total Cost: $12+14 = 26$. Test case $2$: The following can be the optimal paths. Friend $1$: $2 \rightarrow 3 \rightarrow 4 \rightarrow 5$, Cost: $2+5+4$$=11$. Friend $2$: $1$, Cost: $0$. Friend $3$: $6$, Cost: $0$. All the nodes are visited. Total Cost: $11+0+0 = 11$. Test case $3$: It is impossible to visit all the nodes with just $1$ friend.

Input	Output
3 5 4 2 1 2 2 2 3 1 3 4 1 4 5 5 6 0 6 6 0 5	4 0 -1