#include <bits/stdc++.h>

using namespace std;

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

int n;
int m;

struct muchie{
int noda;
int nodb;
long long val;
};
muchie a[1000005];

int cmp(muchie A , muchie B)
{
    return A.val<B.val;
}

long long sum;
muchie rez[1000005];

int parinte[1000005];


int Find(int nod)
{
    int copienod=nod;
    while(parinte[nod]!=0)
    {
        nod=parinte[nod];
    }
    while(parinte[copienod]!=0)
    {
        int aux=copienod;
        copienod=parinte[copienod];
        parinte[aux]=nod;
    }
    return nod;


}

void Union(int x , int y)
{
    parinte[x]=y;
}




int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        long long x , y , v;
        f>>x>>y>>v;
        a[i].noda=x;
        a[i].nodb=y;
        a[i].val=v;

    }
    sort(a+1 , a+m+1 , cmp);

    int bagate=0;
    for(int i=1;i<=m;++i)
    {
        int par1=Find(a[i].noda);
        int par2=Find(a[i].nodb);

        if(par1!=par2)
        {
            ++bagate;
            Union(par1 , par2);
            rez[bagate]=a[i];
            sum+=a[i].val;
        }

        if(bagate==n-1)
            break;
    }

    g<<sum<<"\n"<<n-1<<"\n";
    for(int i=1;i<=bagate;++i)
    {
        g<<rez[i].nodb<<" "<<rez[i].noda<<"\n";

    }
    return 0;
}