Hint1
考虑存在欧拉回路的充要条件。Hint2
当我们想在 $(u, v)$ 点间进行传送时，如何计算最小的代价呢？Hint3
相信你已经通过 Hint2 想到建重构树了，那么不妨试试通过贪心算出答案。转化之后题目要求的就是原图的一个欧拉回路，那我们考虑欧拉回路的充要条件，即每个点的度数都是偶数。那么我们的操作 2 就是用来解决度数问题的。具体来说，我们不妨将传送操作看成在两个点之间添加了一条虚拟边，并同时令两个点的度数 \(+1\)，这样我们每一次操作就可以令两个奇度点变成两个偶度点。
有的同学可能有疑问了，假设现在有奇度点 \(x,z\) 和一个偶度点 \(y\)，那么为什么不能连边 \((x,y),(y,z)\)，这样依然满足点的度数全部为偶。
事实上，这样确实满足了度数要求，但答案不一定最小，因为经过 \(y\) 点的方案实际上已经被包括在连边 $ x \to z$ 的所有方案中了（因为我们连边时考虑的是最小边权。）
那么，如何计算两个点传送的最小代价呢？如果我们把边按照编号排序，并以此建立重构树（类似 Kruskal 重构树中按边权排序），那么任意一条重构树上的路径都对应原图中的一条路径。所以，如果令现在要在 \(u, v\) 间连边，它们在重构树上的 LCA 为 \(x\)，那么最小代价一定是 \(x\) 及其祖先们所代表的边中的最小值。
如此一来，我们令 \(dp_u\) 表示重构树上根到点 \(u\) 所有边权中的最小值，那么一定有 \(dp_u \le dp_{fa_u}\)，那么两个点一定在越深的地方连边越好，基于这个事实，我们直接自底向上 dfs，能合并就直接合并，答案就是最小的。
下面是代码：
// 如果命运对你缄默, 那就活给他看。
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int LL
const int maxn = 2e6 + 10;
int n, m, f[maxn], dp[maxn];
int ans = 0, tot, d[maxn];
bitset<maxn>vs;
vector<int>e[maxn];
inline int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
inline int dfs(int u) {assert(dp[u] <= dp[f[u]]); vs[u] = 1;if(!e[u].size()) {if(d[u] & 1) return u; return 0; }int x = e[u][0]; dp[x] = min(dp[x], dp[u]); if(e[u].size() == 1) return dfs(x);int y = e[u][1]; dp[y] = min(dp[y], dp[u]);x = dfs(x), y = dfs(y); if(!x || !y) return x | y;ans += dp[u]; return 0;
}
inline void solve() {cin >> n >> m;for(int i = 1; i <= n; ++ i) f[i] = i; tot = n;for(int i = 1; i <= m; ++ i) {int u, v, w;cin >> u >> v >> w;d[u] ++, d[v] ++ ;ans += w;u = find(u), v = find(v);tot ++, dp[tot] = w, f[tot] = tot;if(u == v) f[u] = tot, e[tot].emplace_back(u); else f[u] = f[v] = tot, e[tot].emplace_back(u), e[tot].emplace_back(v); // cerr << "adding " << i << ' ' << u << ' ' << v << '\n';}for(int i = tot; i; -- i) if(!vs[i]) dfs(i); cout << ans << '\n';
}
inline void clear() {ans = 0; for(int i = 1; i <= tot; ++ i) vs[i] = dp[i] = f[i] = d[i] = 0, e[i].clear(); tot = 0;
}
signed main() {// freopen(".in", "r", stdin);// freopen(".out", "w", stdout);ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1; cin >> T; while(T--) clear(), solve();return 0;
}