CF2164E.Journey

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:

1. Mark an edge connecting $x$ and $y$, take photos along the edge, and move to $y$, which costs exactly the edge's weight.
2. 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.

你位于一个包含 $n$ 个顶点和 $m$ 条带权无向边的连通图上。这些边从 $1$ 到 $m$ 编号。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，权重为 $w_i$。你决定在该图上开启一场美妙的旅程。

假设你当前位于顶点 $x$，你可以任意次执行以下操作：

1. 标记一条连接 $x$ 和 $y$ 的边，沿该边拍摄照片，并移动到 $y$，花费恰好等于该边的权重。
2. 乘坐火车转移到另一个任意顶点 $z \neq x$。你可以选择任意一条路径 $x\leadsto z$（该路径不一定是简单路径），花费为该路径上边编号最大者所对应边的权重。形式化地，假设你选择的路径包含边编号序列 $e_1, e_2, \ldots, e_k$，且存在顶点序列 $p_1, p_2, \ldots, p_{k+1}$ 满足 $x = p_1$、$z = p_{k+1}$，并且对所有 $i \in [1, k]$，边 $e_i$ 连接 $p_i$ 和 $p_{i+1}$，则花费为 $w_{\max_{i=1}^k e_i}$。

你当前位于顶点 $1$，需要至少标记每条边一次，并最终返回顶点 $1$。请计算最小总花费。

请注意：转移操作的花费既不是路径上的最大边权，也不是最大边编号本身，而是最大边编号所对应边的权重。如有疑问，请参阅下方“注意”部分。

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-loops and multiple edges.

It is guaranteed that the sums of $n$ and $m$ over all test cases do not exceed $10^6$ each.

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$（$1 \le T \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$0 \le m \le 10^6$）。

接下来是 $m$ 行，其中第 $i$ 行包含三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$，$1 \le w \le 10^9$），表示编号为 $i$ 的边连接顶点 $u_i$ 和顶点 $v_i$，其权重为 $w_i$。

保证所描述的图是连通的。

还需注意：该图可能包含自环和重边。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $10^6$。

For each test case output one integer — the minimum cost.

对于每个测试用例，输出一个整数——最小代价。

Visualizer link

Let $u \xrightarrow{e} v$ denote going to vertex $v$ from vertex $u$ by edge $e$.

In the first test case, one possible solution is:

1. Initially, you are at vertex $1$.
2. Mark edge $3$ and move to vertex $3$, costs $6$.
3. Mark edge $6$ and move to vertex $4$, costs $7$.
4. Mark edge $1$ and move to vertex $2$, costs $15$.
5. Mark edge $4$ and move to vertex $3$, costs $9$.
6. Transfer to vertex $5$. By choosing path $3 \xrightarrow{6} 4 \xrightarrow{1} 2 \xrightarrow{2} 5$, we can achieve cost $7$, since the maximum index among the edges on the path is $6$, and $w_6 = 7$. Note that we don't care about the maximum weight on the path when using operation 2.
7. Mark edge $2$ and move to vertex $2$, costs $4$.
8. Mark edge $5$ and move to vertex $1$, costs $10$.

The total cost is $6+7+15+9+7+4+10=58$.

In the second test case, one possible solution is:

1. Mark edge $1$ and move to vertex $2$, costs $3$.
2. Transfer to vertex $3$ by $2 \xrightarrow{1} 1 \xrightarrow{3} 4 \xrightarrow{3} 1 \xrightarrow{2} 3$, costs $1$. Note the path chosen in operation 2 may not be simple.
3. Mark edge $2$ and move to vertex $1$, costs $2$.
4. Mark edge $3$ and move to vertex $4$, costs $1$.
5. Transfer to vertex $1$ by $4 \xrightarrow{3} 1$, costs $1$.

可视化链接

记 $u \xrightarrow{e} v$ 表示通过边 $e$ 从顶点 $u$ 到达顶点 $v$。

在第一个测试用例中，一种可能的解法是：

1. 初始时，你位于顶点 $1$。
2. 标记边 $3$ 并移动到顶点 $3$，花费为 $6$。
3. 标记边 $6$ 并移动到顶点 $4$，花费为 $7$。
4. 标记边 $1$ 并移动到顶点 $2$，花费为 $15$。
5. 标记边 $4$ 并移动到顶点 $3$，花费为 $9$。
6. 转移到顶点 $5$。选择路径 $3 \xrightarrow{6} 4 \xrightarrow{1} 2 \xrightarrow{2} 5$，可实现花费 $7$，因为该路径上所有边的最大编号为 $6$，且 $w_6 = 7$。注意：在执行操作 2 时，我们不关心路径上的最大边权。
7. 标记边 $2$ 并移动到顶点 $2$，花费为 $4$。
8. 标记边 $5$ 并移动到顶点 $1$，花费为 $10$。

总花费为 $6+7+15+9+7+4+10=58$。

在第二个测试用例中，一种可能的解法是：

1. 标记边 $1$ 并移动到顶点 $2$，花费为 $3$。
2. 通过路径 $2 \xrightarrow{1} 1 \xrightarrow{3} 4 \xrightarrow{3} 1 \xrightarrow{2} 3$ 转移到顶点 $3$，花费为 $1$。注意：操作 2 中所选路径未必是简单路径。
3. 标记边 $2$ 并移动到顶点 $1$，花费为 $2$。
4. 标记边 $3$ 并移动到顶点 $4$，花费为 $1$。
5. 通过路径 $4 \xrightarrow{3} 1$ 转移到顶点 $1$，花费为 $1$。