ปิดถนนกันซ้อม: ขอบเขตที่ดูเป็นของแถม คือกุญแจของทั้งข้อ

// ตัวตรวจสอบที่ไม่เชื่อทฤษฎีอะไรเลย ใช้ได้แค่กราฟจิ๋ว ๆ ตอนสุ่มเทียบก่อนส่ง
// ไล่ทุกวิธีเลือกว่าจะ "เก็บ" ถนนไม่ราดยางเส้นไหนไว้บ้าง แล้วไล่หาวงจรอย่างง่ายทุกวง
// ถ้าเจอวงยาวคู่แม้แต่วงเดียวก็ตัดทิ้ง ที่เหลือค่อยเอาน้ำหนักที่เก็บได้มากที่สุด
#include <bits/stdc++.h>
using namespace std;
int n;
vector<array<int,2>> E;                     // เส้นเชื่อมของกราฟที่กำลังตรวจ
vector<vector<pair<int,int>>> adj;          // (เพื่อนบ้าน, หมายเลขเส้น)
bool found;

void walk(int start, int cur, vector<char>& usedEdge, vector<char>& vis, int len) {
    for (auto& [w, ei] : adj[cur]) {
        if (usedEdge[ei]) continue;
        if (w == start) { if (len + 1 >= 2 && (len + 1) % 2 == 0) found = true; continue; }
        if (vis[w] || w < start) continue;   // บังคับให้ปมเล็กสุดของวงเป็นจุดเริ่ม กันนับซ้ำ
        vis[w] = 1; usedEdge[ei] = 1;
        walk(start, w, usedEdge, vis, len + 1);
        vis[w] = 0; usedEdge[ei] = 0;
        if (found) return;
    }
}
bool hasEvenCycle() {
    found = false;
    for (int s = 1; s <= n && !found; s++) {
        vector<char> usedEdge(E.size(), 0), vis(n + 1, 0);
        vis[s] = 1;
        walk(s, s, usedEdge, vis, 0);
    }
    return found;
}
int main() {
    int m; scanf("%d %d", &n, &m);
    vector<array<int,3>> tree, extra;
    long long total = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        if (c == 0) tree.push_back({a, b, c});
        else { extra.push_back({a, b, c}); total += c; }
    }
    long long best = 0;
    for (int mask = 0; mask < (1 << (int)extra.size()); mask++) {
        E.clear();
        for (auto& e : tree) E.push_back({e[0], e[1]});
        long long w = 0;
        for (size_t j = 0; j < extra.size(); j++)
            if (mask >> j & 1) { E.push_back({extra[j][0], extra[j][1]}); w += extra[j][2]; }
        adj.assign(n + 1, {});
        for (size_t i = 0; i < E.size(); i++) {
            adj[E[i][0]].push_back({E[i][1], (int)i});
            adj[E[i][1]].push_back({E[i][0], (int)i});
        }
        if (!hasEvenCycle()) best = max(best, w);
    }
    printf("%lld\n", total - best);
}

#include <bits/stdc++.h>
using namespace std;
int n,mE;
vector<int> ch[1005];              // ลูกของแต่ละปม
int par[1005],dep[1005],idxInPar[1005];
vector<vector<int>> dp;            // dp[v][mask]
struct Ex{ int a,b,w,lca,sa,sb; }; // sa,sb = บิตของลูกที่เส้นทางใช้ (0 ถ้าไม่มี)
vector<Ex> exAt[1005];
vector<pair<int,int>> tadj[1005];

void bfsTree(){
    vector<int> st{1}; par[1]=0; dep[1]=0;
    vector<char> vis(n+1,0); vis[1]=1;
    for(size_t i=0;i<st.size();i++){ int u=st[i];
        for(auto&[v,w]:tadj[u]) if(!vis[v]){ vis[v]=1; par[v]=u; dep[v]=dep[u]+1; idxInPar[v]=(int)ch[u].size(); ch[u].push_back(v); st.push_back(v); }
    }
}
int lcaOf(int a,int b){ while(dep[a]>dep[b]) a=par[a]; while(dep[b]>dep[a]) b=par[b]; while(a!=b){ a=par[a]; b=par[b]; } return a; }
// ผลรวม dp ของปมบนเส้นทางจาก x ขึ้นไปหา v (ไม่รวม v) โดยแต่ละปมห้ามใช้ลูกที่เส้นทางเพิ่งผ่านมา
long long pathSum(int x,int v,int&firstChild){
    long long s=0; int prev=-1; firstChild=0;
    while(x!=v){ int mask = prev<0 ? 0 : (1<<idxInPar[prev]); s+=dp[x][mask]; prev=x; x=par[x]; }
    if(prev>=0) firstChild = 1<<idxInPar[prev];
    return s;
}
int main(){
    scanf("%d %d",&n,&mE);
    vector<array<int,3>> extra;
    long long total=0;
    for(int i=0;i<mE;i++){ int a,b,c; scanf("%d %d %d",&a,&b,&c);
        if(c==0){ tadj[a].push_back({b,0}); tadj[b].push_back({a,0}); }
        else { extra.push_back({a,b,c}); total+=c; } }
    bfsTree();
    for(auto&e:extra){
        int a=e[0],b=e[1],w=e[2],l=lcaOf(a,b);
        int len=dep[a]+dep[b]-2*dep[l];
        if(len%2==1) continue;                       // เส้นทางยาวคี่ วงจะเป็นคู่ ต้องตัดทิ้งเสมอ
        exAt[l].push_back({a,b,w,l,0,0});
    }
    dp.assign(n+1,{});
    // ไล่แบบ post-order ด้วยสแต็ก
    vector<int> order; order.reserve(n); { vector<int> st{1}; while(!st.empty()){ int u=st.back(); st.pop_back(); order.push_back(u); for(int c:ch[u]) st.push_back(c); } }
    for(int i=(int)order.size()-1;i>=0;i--){
        int v=order[i]; int k=(int)ch[v].size(); int full=1<<k;
        vector<long long> d0(k); long long sum=0;
        for(int j=0;j<k;j++){ d0[j]=dp[ch[v][j]][0]; sum+=d0[j]; }
        vector<long long> g(full);
        for(int mk=0;mk<full;mk++){ long long s=sum; for(int j=0;j<k;j++) if(mk>>j&1) s-=d0[j]; g[mk]=s; }
        // เตรียมค่าของเส้นพิเศษที่มี lca = v
        struct Cand{ int se; long long val; };
        vector<Cand> cs;
        for(auto&e:exAt[v]){
            int ca=0,cb=0;
            long long s=pathSum(e.a,v,ca)+pathSum(e.b,v,cb);
            cs.push_back({ca|cb, s+e.w});
        }
        for(int mk=full-1;mk>=0;mk--)
            for(auto&c:cs) if(!(c.se&mk)) g[mk]=max(g[mk],c.val+g[mk|c.se]);
        dp[v]=vector<int>(full);
        for(int mk=0;mk<full;mk++) dp[v][mk]=(int)g[mk];
    }
    printf("%lld\n", total - dp[1][0]);
}