#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
typedef struct
{
    int X,Y,Cost;
}triplet;
vector <triplet> v,APM;
int *r,*d,N;
 triplet T;
    int i,M,cntAPM=0,costAPM=0;
int cautare(int nr)
{
    while(d[nr]!=nr)
    {
        nr=d[nr];
    }
    return nr;
}
bool myFunction(triplet a,triplet b)
{
    return (a.Cost<b.Cost);
}
void reuneste(int x,int y)
   {
       if(r[x]<r[y])
    {
        d[x]=y;
    }
     if(r[y]<r[x])
    {
        d[y]=x;
    }
     if(r[x]==r[y])
    {
        d[x]=y;
        r[y]++;
    }
}
int main()
{

    ifstream fin("shuffle2.in");
    ofstream fout("shuffle2.out");
    fin>>N>>M;
    r=new int[N+1];
    d=new int[N+1];
    for(i=0;i<M;i++)
    {
        fin>>T.X>>T.Y>>T.Cost;
        v.push_back(T);
    }
   // cout<<1;
    sort(v.begin()+1,v.begin()+M+1,myFunction);
    //cout<<1;
    for(i=1;i<=N;i++)
    {

        r[i]=1;
        d[i]=i;
    }
   // cout<<1;
    for(i=1;i<=M;i++)
    {
       //  cout<<1;
       int p,q;
       p=cautare(v[i].X);
       q=cautare(v[i].Y);
        if(p!=q)
        { //cout<<1<<'\n';
             reuneste(p,q);
            // cout<<1<<'\n';
            APM.push_back(v[i]);
            //cout<<APM.size()<<'\n';
            costAPM+=v[i].Cost;
        }


    }
    fout<<costAPM<<'\n';
    fout<<N-1<<'\n';
    for(i=1;i<=N-1;i++)
    {
        fout<<APM[i].X<<' '<<APM[i].Y<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}