You are on an undirected connected graph of (n) vertices and (m) weighted edges. The edges are indexed from (1) to (m). The (i)-th edge connects vertex (u_i) and (v_i), and has weight (w_i). You decided to take a wonderful journey around the graph. Suppose you are at vertex (x). You can do the following operations any number of times: Mark an edge connecting (x) and (y), take photos along the edge, and move to (y), which costs exactly the edge's weight. Transfer to another arbitrary vertex (z \neq x) by train. You may choose any path (x\leadsto z) ( not necessarily simple ), and the cost is the weight of the edge with the maximum index on that path. Formally, suppose you choose the path with edge indices (e_1, e_2, \ldots, e_k), such that there exists an array of vertices (p_1, p_2, \ldots, p_{k+1}) where (x = p_1), (z = p_{k+1}), and for all (i) in (1, k), edge (e_i) connects (p_{i}) and (p_{i+1}), the cost is (w_{\max_{i=1}^k e_i}). You are now at vertex (1), and you need to mark every edge at least once and return to vertex (1). Calculate the minimum cost. Please note the cost for transferring is not the maximum weight on the path, nor the maximum index itself. If you have any questions, refer to the Note section below. Each test contains multiple test cases. The first line contains the number of test cases (T) ((1 \le T \le 10^4)). The description of the test cases follows. The first line of each test case contains two integers (n) and (m) ((1 \le n \le 10^6), (0 \le m \le 10^6)). Then (m) lines, the (i)-th line contains three integers (u_i, v_i, w_i) ((1 \le u_i, v_i \le n), (1 \le w \le 10^9)) — meaning that the edge with index (i) is between vertex (u_i) and vertex (v_i) with weight (w_i). It's guaranteed that the described graph is connected. Also note that the graph may have self-loop