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

using namespace std;

int strastrastrabunic(int x,vector<int> & Pred)
{
    if(Pred[x]==x)
        return Pred[x];
    Pred[x]=strastrastrabunic(Pred[x],Pred);
    return Pred[x];
}

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

void J888(int x,int y,vector<int> & pred)
{
    pred[strastrastrabunic(x,pred)]=strastrastrabunic(y,pred);
}

int main() {
    vector<pair<int,pair<int,int>>> Muchiile;   //(cost, (x, y))
    vector<pair<int,int>>M2;
    vector<int>Predecesor;
    ifstream input("apm.in");
    int N,M,x,y,c,S=0;
    input>>N>>M;
    Muchiile.resize(M+1);
    Predecesor.resize(N+1);
    int i;
    for(i=1;i<=N;i++)
        Predecesor[i]=i;
    for(i=1;i<=M;i++)
    {
        input>>x>>y>>c;
        Muchiile.push_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,Predecesor)!=strastrastrabunic(muchie.second.second,Predecesor))
        {
            M2.push_back(make_pair(muchie.second.first,muchie.second.second));
            J888(muchie.second.first,muchie.second.second,Predecesor);
            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;
}