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

using namespace std;

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

int dad[200010],range[200010];

int find(int nod)
{
    if(dad[nod]!=nod)
    {
        return find(dad[nod]);
    }
    return dad[nod];
}

void reuniune(int nod1,int nod2)
{
    nod1=find(nod1);
    nod2=find(nod2);

    if(range[nod1]>range[nod2])
    {
        dad[nod2]=nod1;
    }
    else if(range[nod2]>range[nod1])
    {
        dad[nod1]=nod2;
    }
    else
    {
        range[nod1]++;
        dad[nod2]=nod1;
    }
}

int n,m,suma;
pair< int , pair < int , int > > muchii[200010];
vector < pair< int, int > > v;


int main()
{

    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        muchii[i].first=z;
        muchii[i].second.first=x;
        muchii[i].second.second=y;
    }

    sort (muchii + 1, muchii + m + 1);

    for(int i=1; i<=n; i++)
    {
        dad[i]=i;
        range[i]=0;
    }

    for(int i=1; i<=m; i++)
    {
         int nod1,nod2;
         nod1=muchii[i].second.first;
         nod2=muchii[i].second.second;
         if(find(nod1)!=find(nod2)){
            suma+=muchii[i].first;
            v.push_back(make_pair(nod1,nod2));
            reuniune(nod1,nod2);
         }
    }
    fout<<suma<<endl;
    fout<<v.size()<<endl;
    for(auto it : v){

        fout<<it.first<<" "<<it.second<<"\n";

    }




}