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

using namespace std;

vector<int>Predecesor;

int strastrastrabunic(int x)
{
    if(Predecesor[x]==x)
        return Predecesor[x];
    Predecesor[x]=strastrastrabunic(Predecesor[x]);
    return 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)
{
    Predecesor[strastrastrabunic(x)]=strastrastrabunic(y);
}

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,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)!=strastrastrabunic(muchie.second.second))
        {
            M2.push_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;
}