#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
struct muchie{int a,b,co;};
muchie G[40001];
int i,j,n,m,A[200001],c[20001],nr,mini,maxi,cost;

void sortaremuchii(int st, int dr)
{
    int i,j;
    muchie x;
    if(st<dr)
        {
            x=G[st]; i=st; j=dr;
            while(i<j)
            {
                while(i<j && G[j ].co>=x.co) j--;
                G[i]=G[j];
                while(i<j && G[i].co<=x.co) i++;
                G[j]=G[i];
            }
            G[i]=x;

        sortaremuchii(st,i-1);
        sortaremuchii(i+1,dr);
        }
}
int main()
{
    f>>n>>m;
    //initializare
    for(i=1;i<=m;i++)
    {
        f>>G[i].a>>G[i].b>>G[i].co;

    }
    for(i=1;i<=n;i++)
        c[i]=i;
    //sortare
    sortaremuchii(1,m);
    nr=0;
    for(i=1;nr<n-1;i++)
        if(c[G[i].a]!=c[G[i].b])
       {

        A[++nr]=i;
    if(c[G[i].a]<c[G[i].b])
    {
        mini=c[G[i].a];
        maxi=c[G[i].b];

    }
    else
    {
        mini=c[G[i].b];
        maxi=c[G[i].a];
    }
    for(j=1;j<=n;j++)
        if(c[j]==maxi) c[j]=mini;
       }
    for(i=1;i<n;i++)
        {
        cost=cost+G[A[i]].co;}
        g<<cost<<endl;
    g<<n-1<<endl;
    for(i=1;i<n;i++)
        g<<G[A[i]].a<<" "<<G[A[i]].b<<endl;
    return 0;
}