TOI16: Water Truck

#include <bits/stdc++.h>

using namespace std;
struct Graph{ int v, w, e; };
const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int inf = 1e9;
using pi = pair <int, int>;
vector <Graph> g[N];
bool bridge[M]; /// edge
bool vs[N];
int deg[N];
void Setting_vs();
int n, m;

int counter = 0;
int disc[N], low[N];
void CutBridge(int u, int prevedge){ /// prevedge (parallel edges)
    counter ++;
    vs[u] = true;
    low[u] = counter;
    disc[u] = counter;
    for(auto vwe: g[u]){
        if(vwe.e == prevedge) continue;
        if(!vs[vwe.v]){
            CutBridge(vwe.v, vwe.e);
            low[u] = min(low[u], low[vwe.v]);
            if(low[vwe.v] > disc[u]) bridge[vwe.e] = true;
        }
        else{
            low[u] = min(low[u], disc[vwe.v]);
        }
    }
}

vector <int> component[N]; // node in component[i]
void DFSComponent(int u, int prevedge, int comp){
    vs[u] = true;
    component[comp].push_back(u);
    for(auto vwe: g[u]){
        if(vs[vwe.v] or vwe.e == prevedge or bridge[vwe.e]) continue;
        DFSComponent(vwe.v, vwe.e, comp);
    }
}

int ShortestPath(int st, int ed){
    Setting_vs();
    priority_queue <pi, vector <pi>, greater <pi>> pq;
    int dis[n + 10]; for(int i=0;i<=n;i++) dis[i] = inf;
    dis[st] = 0;
    pq.push({dis[st], st});
    while(!pq.empty()){
        int d = pq.top().first, u = pq.top().second; pq.pop();
        if(vs[u]) continue; vs[u] = true;
        if(u == ed) return d;
        for(auto vwe: g[u]){
            if(bridge[vwe.e]) continue;
            if(!vs[vwe.v] and d + vwe.w < dis[vwe.v]){
                dis[vwe.v] = d + vwe.w;
                pq.push({dis[vwe.v], vwe.v});
            }
        }
    }
}

int main(){

    scanf("%d %d", &m, &n);

    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        g[u].push_back({v, w, i});
        g[v].push_back({u, w, i});
    }

    CutBridge(0, 0);

    Setting_vs();

    int sumbridge = 0;
    int sumedge = 0;
    int ncomponent = 0;
    for(int u=0;u<=n;u++){
        for(auto vwe: g[u]){
            if(bridge[vwe.e]) sumbridge += vwe.w;
            else{
                sumedge += vwe.w;
                deg[u] ++;
            }
        }
        if(!vs[u]){
            ncomponent ++;
            DFSComponent(u, 0, ncomponent);
        }
    }
    sumbridge /= 2;
    sumedge /= 2;

    int sumodddeg = 0;
    for(int i=1;i<=ncomponent;i++){
        vector <int> odddeg;
        for(auto node: component[i]){
            if(deg[node] % 2 == 1) odddeg.push_back(node);
        }
        if(odddeg.size() == 2)
            sumodddeg += ShortestPath(odddeg[0], odddeg[1]);
        else if(odddeg.size() == 4){
            int type1 = ShortestPath(odddeg[0], odddeg[3]) + ShortestPath(odddeg[1], odddeg[2]);
            int type2 = ShortestPath(odddeg[0], odddeg[1]) + ShortestPath(odddeg[2], odddeg[3]);
            int type3 = ShortestPath(odddeg[0], odddeg[2]) + ShortestPath(odddeg[1], odddeg[3]);
            sumodddeg += min({type1, type2, type3});
        }
    }

    printf("%d", 2 * sumbridge + sumedge + sumodddeg);

    return 0;
}


void Setting_vs(){
    for(int u=0;u<=n;u++) vs[u] = false;
}