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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85// brute.cpp：每一周都把前缀边重新跑一遍 Kruskal。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXM = 105;

struct Edge {
    int u, v, w;

    bool operator<(const Edge &other) const {
        return w < other.w;
    }
} edges[MAXM];

int n, weeks;
int fa[MAXN];

void init_dsu() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

bool unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
        return false;
    }
    fa[x] = y;
    return true;
}

long long solve_prefix(int cnt) {
    vector<Edge> a;
    for (int i = 1; i <= cnt; i++) {
        a.push_back(edges[i]);
    }
    sort(a.begin(), a.end());

    init_dsu();
    int used = 0;
    long long sum = 0;

    for (int i = 0; i < (int)a.size(); i++) {
        if (!unite(a[i].u, a[i].v)) {
            continue;
        }
        used++;
        sum += a[i].w;
        if (used == n - 1) {
            break;
        }
    }

    if (used != n - 1) {
        return -1;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> weeks;
    for (int i = 1; i <= weeks; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    for (int i = 1; i <= weeks; i++) {
        cout << solve_prefix(i) << '\n';
    }

    return 0;
}

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

struct Edge {
    int u, v, w;
};

int n, weeks;
vector<Edge> forest;
long long total_weight = 0;

vector<pair<int, int>> graph[MAXN];
bool vis[MAXN];
int parent_node[MAXN];
int parent_edge[MAXN];

void build_graph() {
    for (int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for (int i = 0; i < (int)forest.size(); i++) {
        Edge &e = forest[i];
        graph[e.u].push_back({e.v, i});
        graph[e.v].push_back({e.u, i});
    }
}

// 如果 u 和 v 当前在同一棵树里，返回路径上权值最大的边编号。
// 否则返回 -1，表示这条新边会连接两个不同连通块。
int max_edge_on_path(int start, int target) {
    build_graph();
    for (int i = 1; i <= n; i++) {
        vis[i] = false;
        parent_node[i] = 0;
        parent_edge[i] = -1;
    }

    queue<int> q;
    q.push(start);
    vis[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == target) {
            break;
        }

        for (pair<int, int> e : graph[u]) {
            int v = e.first;
            int id = e.second;
            if (vis[v]) {
                continue;
            }
            vis[v] = true;
            parent_node[v] = u;
            parent_edge[v] = id;
            q.push(v);
        }
    }

    if (!vis[target]) {
        return -1;
    }

    int best_id = -1;
    int cur = target;
    while (cur != start) {
        int id = parent_edge[cur];
        if (best_id == -1 || forest[id].w > forest[best_id].w) {
            best_id = id;
        }
        cur = parent_node[cur];
    }

    return best_id;
}

void add_new_edge(Edge e) {
    int id = max_edge_on_path(e.u, e.v);

    if (id == -1) {
        forest.push_back(e);
        total_weight += e.w;
        return;
    }

    if (forest[id].w > e.w) {
        total_weight += e.w - forest[id].w;
        forest[id] = e;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> weeks;

    for (int i = 1; i <= weeks; i++) {
        Edge e;
        cin >> e.u >> e.v >> e.w;
        add_new_edge(e);

        if ((int)forest.size() == n - 1) {
            cout << total_weight << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

    return 0;
}