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

using namespace std;

vector<int>Predecesor,inaltime;

int strastrastrabunic(int x)
{
    if(Predecesor[x]==x)
        return Predecesor[x];
    return Predecesor[x]=strastrastrabunic(Predecesor[x]);
}

bool cmp(pair<short int,pair<int,int>>x,pair<short int,pair<int,int>>y)
{
    return x.first<y.first;
}

void J888(int x,int y)
{
    int xx=strastrastrabunic(x);
    int yy=strastrastrabunic(y);
    if(xx==yy)
        return;
    if(inaltime[xx]<inaltime[yy])
        Predecesor[xx]=yy;
    else if(inaltime[xx]>inaltime[yy])
        Predecesor[yy]=xx;
    else
    {
        Predecesor[yy]=xx;
        inaltime[xx]++;
    }
}

int main() {
    vector<pair<short int,pair<int,int>>> Muchiile;   //(cost, (x, y))
    vector<pair<int,int>>M2;
    ifstream input("apm.in");
    int N,M,S=0;
    int x,y;
    short int c;
    input>>N>>M;
    Predecesor.reserve(N+1);
    inaltime.resize(N+1);
    Muchiile.reserve(M+1);
    int i;
    for(i=1;i<=N;i++)
        Predecesor[i]=i;
    for(i=1;i<=M;i++)
    {
        input>>x>>y>>c;
        Muchiile.emplace_back(make_pair(c,make_pair(x,y)));
    }
    input.close();
    sort(Muchiile.begin(),Muchiile.end(),cmp);
    for(pair<int,pair<int,int>> muchie:Muchiile)
    {
        if(strastrastrabunic(muchie.second.first)!=strastrastrabunic(muchie.second.second))
        {
            M2.emplace_back(make_pair(muchie.second.first,muchie.second.second));
            J888(muchie.second.first,muchie.second.second);
            S=S+muchie.first;
        }
    }
    ofstream output("apm.out");
    output<<S<<endl<<M2.size()<<endl;
    for(pair<int,int>J8888:M2)
        output<<J8888.first<<" "<<J8888.second<<endl;
    output.close();
    return 0;
}