太好了，一晚上写了一道题，感觉至少是紫题，一看只是 *2300，甚至洛谷上评的蓝……但这不妨碍是一道很好的题。

首先，很明显如果存在欧拉回路的话就是直接把每一条边都走一遍就好了。如果不是的话，那必然有偶数个奇度点（$a_1+2a_2=2m$，所以 $2\mid a_1$）。

那我们考虑在每条边都走的基础上，在奇度点使用操作 2 就好了。我们可以把一次传送看作加一条边，一次传送会让那两个点的度数都 $+1$ 变为偶度点，这样既可以让原图变成欧拉图，还刚好不会多加度数。

那传送代价怎么弄最小呢？观察题目，权值是路径上最大编号的边的边权，最小化最大边权，不就是最小瓶颈路吗？以编号为序使用 kruskal 重构树即可（一道板子题）。重构树上的 LCA 即是路径权值。
由于这里是编号来排序，边权未必最小，我们考虑如果已经当前这条边的两端已经联通的情况。目前枚举到的编号一定大于之前的，所以如果使用这条边的话连通块的权值一定变为这条边的边权，如果权值更小那我们就采用就好了。路径的权值更新在他们的 LCA 上。

最后的计算部分，类似树形 DP。dfs 时遍历到的点作为下面点的 LCA，如果一颗子树下面的奇度点数是奇数（即还有未变成偶度点的），那就让它和另一颗子树中剩余的奇度点匹配即可。传送的最小代价是 LCA 到根中的最小权值（因为重构树父节点编号一定比子节点大，值小可以取）。令 $a_v$ 表示以 $v$ 为根的子树下是否有剩余的奇度点，进行 $\lfloor \frac{\sum a_v}{2}\rfloor$ 次传送即可，剩余的奇度点往上传。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+5,inf=1e9;
struct DSU{
    int fa[N],sz[N];
    void reset(int n){
        for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    }
    int find(int x){
        return (fa[x]==x?x:fa[x]=find(fa[x]));
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y) return;
        if(sz[x]<sz[y]) swap(x,y);
        fa[y]=x,sz[x]+=sz[y];
    }
}mk;
int n,m,val[N],f[N],sz[N],deg[N];
vector<int> g[N];
ll ans;
void dfs(int u,int mnw){
    mnw=min(mnw,val[u]);
    sz[u]=deg[u]%2;
    for(int v:g[u]){
        dfs(v,mnw);
        sz[u]+=sz[v];
    }
    ans+=1ll*sz[u]/2*mnw;
    sz[u]%=2;
}
void solve(){
    cin>>n>>m;
    mk.reset(n+m);
    for(int i=1;i<=n+m;i++) val[i]=inf,f[i]=i,g[i].clear(),sz[i]=deg[i]=0;
    ans=0;
    int tot=n;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        deg[u]++;deg[v]++;ans+=w;
        u=mk.find(u),v=mk.find(v);
        if(u!=v){
            tot++;
            g[tot].push_back(f[u]);
            g[tot].push_back(f[v]);
            mk.merge(u,v);
            val[tot]=w;
            f[mk.find(u)]=tot;
        }
        else val[f[u]]=min(val[f[u]],w);
    }
    dfs(tot,inf);
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}