#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");
struct muchie
{
    int st,dr,cost;
};
muchie e[400002],alese [200001];
int tata[200001];
int x,y,c,n,m,p1,p2,nralese,suma;
int nrniv[200001];
int found(int x)
{
    int r=x;
    while(tata[r]!=0)
        r=tata[r];
    int y;
    while(tata[x]!=0)
    {
        y=tata[x];
        tata[x]=r;
        x=y;
    }
    return r;
}
void uniune(int r1,int r2)
{
    if(nrniv[r1]<nrniv[r2])
        tata[r1]=r2;
    else if(nrniv[r2]<nrniv[r1])
        tata[r2]=r1;
    else
    {
        tata[r2]=r1;
        nrniv[r1]++;

    }

}
int cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    in>>e[i].st>>e[i].dr>>e[i].cost;
    sort(&e[1],&e[m+1],cmp);
    for(int i=1;i<=m && nralese<n-1;i++)
    {   p1=found(e[i].st);
        p2=found(e[i].dr);
        if(p1!=p2)
        {nralese++;
        alese[nralese]=e[i];
        suma=suma+e[i].cost;
        uniune(p1,p2);
        }

    }
    out<<suma<<'\n';
    out<<n-1<<'\n';
    for(int i=1;i<=n-1;i++)
        {

        out<<alese[i].dr<<" "<<alese[i].st<<'\n';}

    return 0;
}