прима за O(nm)

#include <iostream>
#include <set>
#include <vector>
#include <deque>
#include <map>
#include <cmath>
#include <random>
#include <algorithm>

#define se second
#define fi first
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, pair<int, int>>> vert(m);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--, y--;
        vert[i] = {w, {x, y}};
    }
    vector<bool> used(n, false);
    used[0] = true;
    vector<pair<int, int>> ostov;
    int answ = 0;
    for (int _ = 0; _ < n - 1; _++) {
        pair<int, pair<int, int>> mn = {10000000, {-1, -1}};
        for (int i = 0; i < m; i++) {
            if (used[vert[i].se.fi] != used[vert[i].se.se]) {
                mn = min(mn, vert[i]);
            }
        }
        ostov.push_back(mn.se);
        answ += mn.fi;
        used[mn.se.fi] = true;
        used[mn.se.se] = true;
    }
    cout << answ << '\n';
    for (auto e : ostov) {
        cout << e.fi + 1 << ' ' << e.se + 1 << '\n';
    }
    return 0;
}