#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

int n,m,total=0,sef[400005],k=0;

struct perechi
{
    int first, second;

}p[400005];

struct muchie {
    int x,y,cost;
}v[400005];

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

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1, v+m+1, compara);

    for(int i=1; i<=n; i++)
    {
        //fout<<v[i].x<<" "<<v[i].y<<" "<<v[i].cost<<endl;
        sef[i]=i;
    }

}

int sefsuprem (int nod)
{
    if (sef[nod]==nod) return nod;
    else
    {
        sef[nod]=sefsuprem (sef[nod]);
        return sef[nod];
    }
}

void unire(int a, int b)
{
    int sefa, sefb;
    sefa=sefsuprem(a);
    sefb=sefsuprem(b);
    sef[sefa]=sefb;
}

void rezolvare()
{
    for(int i=1 ;i<=m; i++)
    {
        int sefx= sefsuprem(v[i].x);
        int sefy= sefsuprem(v[i].y);
        if(sefx!=sefy)
        {
            unire(sefx, sefy);
            p[++k].first=v[i].x;
            p[k].second=v[i].y;
            total= total+ v[i].cost;
        }
    }
}

void afisare()
{
    fout<<total<<"\n";
    fout<<n-1<<"\n";
    for(int i=1; i<=k; i++)
        fout<< p[i].second<<" "<<p[i].first<<"\n";
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}