#include <fstream>
#define MaxN 200001
#define MaxM 400001
using namespace std;

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

struct muchie
{
    int a,b,c;
};
muchie M[MaxM];

int n,m, tata[MaxN], A[MaxN], B[MaxN],k;

long int cost;

void sort()
{
    int i,j;
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
            if(M[i].c>M[j].c)
                swap(M[i],M[j]);
}
int tatuca(int x)
{
    if(tata[x]!=x) tata[x]=tatuca(tata[x]);
    return tata[x];
}
void apm()
{
    int i, ta, tb;
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=1;i<=m;i++)
    {
        ta=tatuca(M[i].a);
        tb=tatuca(M[i].b);
        if(ta!=tb)
        {
            cost=cost+M[i].c;
            k++;
            A[k]=M[i].a;
            B[k]=M[i].b;
            tata[ta]=tb;
        }
    }
}
int main()
{
    int a,b,c,i,j;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        M[i].a=a;
        M[i].b=b;
        M[i].c=c;
    }
    in.close();
    sort();
    apm();
    out<<cost<<"\n";
    out<<n-1<<"\n";
    for(i=1;i<=k;i++)
        out<<B[i]<<" "<<A[i]<<"\n";
    out.close();
    return 0;
}