#include<fstream>

using namespace std;

const char iname[]="apm.in";
const char oname[]="apm.out";
const int maxn=100005;
const int maxm=400005;

ifstream f(iname);
ofstream g(oname);

struct muchie
{
    int x;
    int y;
    int c;
}E[maxm];

bool operator<(const muchie& a,const muchie& b)
{
    return a.c<b.c;
}

int A[maxn],L[maxn],i,j,n,m,total,answer[maxn][2],k;

int anc(int x)
{
    int y,a;
    for(a=x;a!=A[a];a=A[a]);

    for(;x!=A[x];)
    {
        y=A[x];
        A[x]=a;
        x=y;
    }

    return a;
}

void merge(int x,int y)
{
    if(L[x]>L[y])
        A[y]=x;
    else
        A[x]=y;

    if(L[x]==L[y])
        ++L[y];
}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;++i)
        f>>E[i].x>>E[i].y>>E[i].c;

    sort(E+1,E+m+1);
    for(i=1;i<=n;++i)
        A[i]=i,L[i]=1;
    for(i=1;i<=m;++i)
        if(anc(E[i].x)!=anc(E[i].y))
            merge(anc(E[i].x),anc(E[i].y)),total+=E[i].c,answer[++k][0]=E[i].x,answer[k][1]=E[i].y;

    g<<total<<"\n"<<n-1<<"\n";
    for(i=1;i<n;++i)
        g<<answer[i][0]<<" "<<answer[i][1]<<"\n";

    f.close();
    g.close();

    return 0;
}