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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int Nmax= 400005;

int N,M,k=0;
int total, TT[Nmax],RG[Nmax];
pair <int,int> sol[Nmax];

struct muchie
{
    int x,y,c;
}v[Nmax];

bool compara(muchie a,muchie b)
{
    return a.c<b.c;
}

void read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }

    sort(v+1,v+M+1,compara);

    for(int i=1;i<=N;i++)
    {
        TT[i]=i;
        RG[i]=1;
    }
}

int findparent(int nod)
{
    while(TT[nod]!=nod)
        nod=TT[nod];
    return nod;
}

void lipeste(int x,int y)
{
    if(RG[y]<RG[x])
        TT[y]=x;
    if(RG[x]<RG[y])
        TT[x]=y;
    if(RG[x]==RG[y])
    {
        TT[x]=y;
        RG[y]++;
    }
}

void rezolva()
{
    for(int i=1;i<=M;i++)
    {
        int tx=findparent(v[i].x);
        int ty=findparent(v[i].y);
        if(tx!=ty)
        {
         lipeste(tx,ty);
         total+=v[i].c;
         sol[++k].first=v[i].x;
         sol[k].second=v[i].y;
        }
    }
    fout<<total<<'\n';
    fout<<N-1<<'\n';
    for(int i=1;i<=N-1;i++)
      fout<<sol[i].second<<" "<<sol[i].first<<'\n';

}

int main()
{
    read();
    rezolva();
    return 0;
}