#include <vector>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,i,j,m,x,y,c,nrc,sol,nrs,r1,r2;
int tata[400005];
struct muchie
{
    int x,y,c;
} mu[400005],ans[400005];
bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

int radacina (int a)
{
    int r=a;
    while(tata[r]!=r)
    {
        r=tata[r];
    }

    while(tata[a]!=a)
    {
        int aux=tata[a];
        tata[a]=r;
        a=aux;
    }

    return r;
}

int main()
{
    cin>>n>>m;
    for(i=1;i<=n;++i) tata[i]=i;
    for(i=1; i<=m; ++i)
    {
        cin>>x>>y>>c;
        mu[i].x=x;
        mu[i].y=y;
        mu[i].c=c;
    }
    sort(mu+1,mu+m+1,cmp);

    for(i=1; i<=m; ++i)
    {
        r1 = radacina(mu[i].x);
        r2 = radacina(mu[i].y);

        if(r1!=r2)
        {
            tata[r1] = r2;
            ++nrs;
            ans[nrs].x = mu[i].x;
            ans[nrs].y = mu[i].y;
            sol+=mu[i].c;
        }
    }

    cout<<sol<<"\n";
    cout<<nrs<<"\n";
    for(i=1; i<=nrs; ++i)
        cout<<ans[i].x<<" "<<ans[i].y <<"\n";
    return 0;
}