problem188

#include <bits/stdc++.h>

using namespace std;


struct Edge
{
    int u, v;
    int w;
    bool operator <(Edge r)
    {
        return w < r.w || (w == r.w && u < r.u) || (w == r.w && u == r.u && v < r.v);
    }
};

vector<int> p;

int get_p(int v)
{
    if (p[v] == v)
        return v;
    return p[v] = get_p(p[v]);
}

void join(int a, int b)
{
    a = get_p(a);
    b = get_p(b);
    if (a == b)
        return;
    if (rand() % 2)
        p[a] = b;
    else
        p[b] = a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<Edge> g(m);
    p.resize(n);
    for (int i = 0; i < n; i++)
        p[i] = i;
    for (int i = 0; i < m; i++)
    {
        cin >> g[i].u >> g[i].v >> g[i].w;
        g[i].v--;
        g[i].u--;
    }
    sort(g.begin(), g.end());
    vector<pair<int, int> >ans;
    int tw = 0;
    for (int i = 0; i < m; i++)
    {
        int u = get_p(g[i].u);
        int v = get_p(g[i].v);
        if (u == v)
            continue;
        join(u, v);
        tw += g[i].w;
        ans.push_back({g[i].u + 1, g[i].v + 1});
    }
    cout << tw << endl;
    for (auto x : ans)
        cout << x.first << " " << x.second << endl;
    return 0;
}