#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

using namespace std;

int x,y,c,n,m;
struct muchie
{
    int x,y,c;
} mu[400100],ans[400100];
int tata[200100];
int total,nrm;

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(a != tata[a])
    {
        int aux = tata[a];
        tata[a] = r;
        a = aux;
    }

    return r;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
        fin>>mu[i].x>>mu[i].y>>mu[i].c;

    sort(mu+1,mu+m+1,cmp);

    for(int i=1;i<=n;++i)
        tata[i] = i;

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

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

    fout<<total<<"\n"<<nrm<<"\n";
    for(int i=1;i<=nrm;++i)
        fout<<ans[i].x<<" "<<ans[i].y<<"\n";

    return 0;
}