Tour De Chittagong

Apurba.884537 CUET CSE Fest 2022 - Inte...
Limits 2s, 512 MB

The city of Chittagong can be considered a weighted directed acyclic graph (DAG) of nn nodes and mm edges. There are kk 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 uu to vv if, the friend is currently in node uu and there is an edge from uu to vv. The cost of this operation is the weight of the edge uvu \rightarrow v.

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

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-1, if it is impossible to visit all the nodes by kk friends.

Input

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

The first line of each test case contains three integers n,mn,m and kk (1n100,0m300,1kn)(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 mm lines describe the edges. Each contains three integers u,v,wu, v, w (1u,vn,uv,1w106)(1 \le u,v \le n, u \ne v, 1 \le w \le 10^6) — the directed edge uvu \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-1. Otherwise, output the minimum total cost to visit all the nodes.

Samples

InputOutput
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 11: The following can be the optimal paths.

Friend 11: 13451 \rightarrow 3 \rightarrow 4 \rightarrow 5, Cost: 3+5+4=123+5+4 = 12.

Friend 22: 23462 \rightarrow 3 \rightarrow 4 \rightarrow 6, Cost: 2+5+7=142+5+7 = 14.

All the nodes are visited. Total Cost: 12+14=2612+14 = 26.

Test case 22: The following can be the optimal paths.

Friend 11: 23452 \rightarrow 3 \rightarrow 4 \rightarrow 5, Cost: 2+5+42+5+4=11=11.

Friend 22: 11, Cost: 00.

Friend 33: 66, Cost: 00.

All the nodes are visited. Total Cost: 11+0+0=1111+0+0 = 11.

Test case 33: It is impossible to visit all the nodes with just 11 friend.

InputOutput
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

Submit

Login to submit.

Statistics

67% Solution Ratio
sh2018331053Earliest, 1M ago
YouKnowWhoFastest, 0.0s
sh2018331053Lightest, 5.6 MB
YouKnowWhoShortest, 3945B
Toph uses cookies. By continuing you agree to our Cookie Policy.