ดูแลทางเดิน: ทางที่ถูกทิ้งไปแล้ว ไม่มีวันกลับมา

#include <bits/stdc++.h>
using namespace std;
int par[205];
int findp(int x){ return par[x] == x ? x : par[x] = findp(par[x]); }
int main(){
    int n, w;
    if(scanf("%d %d", &n, &w) != 2) return 0;
    // เก็บแค่เส้นของต้นไม้ปัจจุบัน เรียงจากสั้นไปยาว เป็น (ความยาว, ปลาย, ปลาย)
    vector<array<int,3>> keep;
    for(int week = 0; week < w; week++){
        int u, v, z;
        scanf("%d %d %d", &u, &v, &z);
        // แทรกเส้นใหม่ลงตำแหน่งของมัน รายการจึงเรียงอยู่เสมอ ไม่ต้อง sort ใหม่
        array<int,3> e = {z, u, v};
        keep.insert(upper_bound(keep.begin(), keep.end(), e), e);
        // Kruskal บนเส้นไม่เกิน N เส้น
        for(int i = 1; i <= n; i++) par[i] = i;
        vector<array<int,3>> tree;
        long long total = 0;
        for(auto &t : keep){
            int a = findp(t[1]), b = findp(t[2]);
            if(a == b) continue;   // เส้นนี้ปิดวง และยาวที่สุดในวงนั้น ทิ้งถาวร
            par[a] = b;
            tree.push_back(t);
            total += t[0];
        }
        keep = tree;
        if((int)tree.size() == n - 1) printf("%lld\n", total);
        else printf("-1\n");
    }
}

#include <bits/stdc++.h>
using namespace std;
int par[205];
int findp(int x){ return par[x] == x ? x : par[x] = findp(par[x]); }
int main(){
    int n, w;
    if(scanf("%d %d", &n, &w) != 2) return 0;
    vector<array<int,3>> all;   // ทุกเส้นที่เคยเจอ ไม่ทิ้งอะไรเลย
    for(int week = 0; week < w; week++){
        int u, v, z;
        scanf("%d %d %d", &u, &v, &z);
        all.push_back({z, u, v});
        // Kruskal ใหม่หมดทุกสัปดาห์ เรียงสำเนาของทุกเส้นที่เคยเจอ
        vector<array<int,3>> es = all;
        sort(es.begin(), es.end());
        for(int i = 1; i <= n; i++) par[i] = i;
        int used = 0;
        long long total = 0;
        for(auto &t : es){
            int a = findp(t[1]), b = findp(t[2]);
            if(a == b) continue;
            par[a] = b;
            used++;
            total += t[0];
        }
        if(used == n - 1) printf("%lld\n", total);
        else printf("-1\n");
    }
}

// ตัวตรวจ ลองทุกเซตย่อยของเส้นที่รู้จัก เลือกเซตที่ทำให้ทุกจุดถึงกันแล้วยาวรวมน้อยที่สุด
// ไม่เรียงเส้น ไม่ทิ้งเส้น ไม่มี Kruskal ใช้ได้กับกราฟเล็ก ๆ เท่านั้น
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, w;
    scanf("%d %d", &n, &w);
    vector<int> U(w), V(w), Z(w);
    for(int k = 0; k < w; k++){
        scanf("%d %d %d", &U[k], &V[k], &Z[k]);
        int m = k + 1;
        long long best = -1;
        for(int mask = 0; mask < (1 << m); mask++){
            // เริ่มจากจุด 1 แล้วแผ่ไปตามเส้นในเซตนี้ซ้ำ ๆ จนไม่มีจุดใหม่
            vector<int> seen(n + 1, 0);
            seen[1] = 1;
            bool grow = true;
            while(grow){
                grow = false;
                for(int i = 0; i < m; i++) if(mask >> i & 1)
                    if(seen[U[i]] != seen[V[i]]){ seen[U[i]] = seen[V[i]] = 1; grow = true; }
            }
            if(count(seen.begin() + 1, seen.end(), 1) != n) continue;
            long long s = 0;
            for(int i = 0; i < m; i++) if(mask >> i & 1) s += Z[i];
            if(best < 0 || s < best) best = s;
        }
        printf("%lld\n", best);
    }
}