B"You are given an undirected connected simple graph with n nodes and m edges, where edge i connects node u_i and v_i , with two positive parameters a_i and b_i attached to it. Additionally, you are also given an integer k . A non-negative array x with size m is called a k -spanning-tree generator if it satisfies the following: The cost of such array x is defined as sum_{i = 1}^m a_i x_i^2 + b_i x_i . Find the minimum cost of a k -spanning-tree generator. ^ dagger A spanning tree of a (multi)graph is a subset of the graph's edges that form a tree connecting all vertices of the graph. Each test contains multiple test cases. The first line contains an integer t ( 1 <= t <= 500 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains three integers n , m , and k ( 2 <= n <= 50, n - 1 <= m <= min(50, frac{n(n - 1)}{2}), 1 <= k <= 10^7 ) -- the number of nodes in the graph, the number of edges in the graph, and the parameter for the k -spanning-tree generator. Each of the next m lines of each test case contains four integers u_i , v_i , a_i , and b_i ( 1 <= u_i, v_i <= n, u_i neq v_i, 1 <= a_i, b_i <= 1000 ) -- the endpoints of the edge i and its two parameters. It is guaranteed that the graph is simple and connected. It is guaranteed that the sum of n^2 and the sum of m^2 over all test cases does not exceed 2500 . For each test case, output a single integer: the minimum cost of a k -spanning-tree generator. In the first test case, a valid 1 -spanning-tree generator is x = [1, 1, 1, 1, 0] , as indicated by the following figure. The cost of this generator is (1^2 cdot 5 + 1 cdot 5) + (1^2 cdot 5 + 1 cdot 7) + (1^2 cdot 6 + 1 cdot 2) + (1^2 cdot 3 + 1 cdot 5) + (0^2 cdot 4 + 0 cdot 9) ="...