#include <bits/stdc++.h>

using namespace std;

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

int N,M,parent[100005],h[100005],i,j,type,a,b,x,y,c,nrm,cost;
vector< array<int,3> > E;
vector< pair<int,int> > muchii;
array<int,3> aux;

int Find(int x){
        if (parent[x] == x) return x;
        return parent[x] = Find(parent[x]);
}

bool Join(int a,int b){
        a = Find(a);
        b = Find(b);

        if (a == b) return 0;

        if (h[a] > h[b])
                parent[b] = a;
        else if (h[a] < h[b])
                parent[a] = b;
        else{
                parent[a] = b;
                h[a]++;
        }
        return 1;
}

bool Same(int a,int b){
        return Find(a) == Find(b);
}

bool comp(array<int,3> a,array<int,3> b){
        return a[2] < b[2];
}

int main()
{
    fin >> N >> M;

    for (i = 1;i <= N;i++){
        parent[i] = i;
        h[i] = 0;
    }

    for (i = 1;i <= M;i++){
        fin >> x >> y >> c;
        aux[0] = x; aux[1] = y; aux[2] = c;
        E.push_back(aux);
    }

    sort(E.begin(),E.end(),comp);

    for (auto k : E){
        aux = k;
        if (Join(aux[0],aux[1])){
                cost += aux[2];
                Join(aux[0],aux[1]);

                muchii.push_back({aux[0],aux[1]});

                nrm++;
        }
    }

        fout << cost << "\n";
        fout << nrm << "\n";

        for (auto k : muchii)
                fout << k.second << " " << k.first << "\n";

    return 0;
}