#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct muchie {
    int a,b,cost;
};

int p[10000001], h[10000001], sol;
vector<pair<int,int>>M;
vector<muchie> L;

int Find(int x) {
    while(x!=p[x])
        x=p[x];
    return x;
}

void Union(int x, int y){
    x=Find(x);
    y=Find(y);
    if(h[x] < h[y])
        p[x]=y;
    else {
        if(h[x] > h[y])
            p[y]=x;
        else
        {
            p[x]=y;
            h[y]++;
        }

    }
}

int main()
{
    int n,m,x,y,c;
    fin>>n>>m;

    for(int i=1;i<=n;i++){
        p[i]=i;
        h[i]=0;
    }
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        L.push_back({x,y,c});
    }

    sort(L.begin(), L.end(), [](const muchie& a, const muchie& b) {return a.cost < b.cost;});

    for(auto Muchie : L){
        if(Find(Muchie.a) != Find(Muchie.b)){
            sol+=Muchie.cost;
            M.push_back({Muchie.a,Muchie.b});
            Union(Muchie.a,Muchie.b);
        }
    }

    fout<<sol<<"\n";
    fout<<M.size()<<"\n";

     for (int i = 0; i < M.size(); i++) {
        fout << M[i].first << " " << M[i].second << "\n";
    }
    fout.close();
}