#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int, int>
#define piii pair<int, pair<int, int> >

using namespace std;

const int N_MAX = 200000 + 5;

priority_queue<piii, vector<piii>, greater<piii> > q;
vector<pii> sol;

ifstream fin ("apm.in");
ofstream fout("apm.out");

int n, m, ans;

int p[N_MAX];

int parinte(int a){
    if(p[a] == a)
        return a;
    return p[a] = parinte(p[a]);
}

int main()
{
    fin >> n >> m;
    while(m--){
        int a, b, c;
        fin >> a >> b >> c;
        p[a] = a; p[b] = b;
        q.push({c, {a,b}});
    }

    while(!q.empty()){
        piii top = q.top();
        q.pop();

        if(parinte(top.y.x) != parinte(top.y.y)){
            p[parinte(top.y.x)] = p[parinte(top.y.y)];
            ans += top.x;
            sol.push_back(top.y);
        }

    }

    fout << ans << "\n";
    fout << sol.size() << "\n";
    for(int i = 0; i<sol.size(); ++i)
        fout << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}