#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m;
struct muchie
{
    int a,b,cost;
} lat[400010];
struct copac
{
    int a,b;
} sol[200010];
int h[200010];
int pater[200010];
int cost;

int comp(muchie x,muchie y)
{
    if(x.cost<y.cost) return 1;
    else return 0;
}

int Vater(int k)
{
    while(k!=pater[k]) return Vater(pater[k]);
    return k;
}

bool approval(int r1,int r2)
{
    r1=Vater(r1);
    r2=Vater(r2);
    if(r1==r2) return false;
    if(h[r1]<h[r2]) pater[r1]=r2;
    else
    {
        if(h[r2]<h[r1]) pater[r2]=r1;
        else
        {
            pater[r1]=r2;
            h[r2]++;
        }
    }
    return true;
}

void cit()
{
    f>>n>>m;
    int i;
    for(i=1; i<=m; i++)
    {
        f>>lat[i].a>>lat[i].b>>lat[i].cost;
        h[i]=1;
        pater[i]=i;
    }
    sort(lat+1,lat+m+1,comp);
}

void kruskal()
{
    int k=1,nrmuchii=1,r1,r2;
    while(nrmuchii<=n-1) //Graful sigur e conex.
    {
        r1=lat[k].a;
        r2=lat[k].b;
        if(approval(r1,r2))
        {
            sol[nrmuchii].a=r1;
            sol[nrmuchii].b=r2;
            nrmuchii++;
            cost=cost+lat[k].cost;


        }
        k++;
    }
}

void afis()
{
    int i;
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=1; i<=n-1; i++) g<<sol[i].a<<" "<<sol[i].b<<'\n';
}

int main()
{
    cit();
    kruskal();
    afis();
    return 0;
}