#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

#define NMAX 401000

using namespace std;

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

struct muchie
{
    int x,y,c;
    bool sem;
}M;

muchie v[NMAX];

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}
//https://dponline.ro/articol.php?idarticol=77
int L[NMAX];
int main()
{
    int n,extr_init,extr_fin,i,cost,suma=0,j,vfx,vfy,varf,k=0,w,m;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>extr_init>>extr_fin>>cost;

        M.x=extr_init;
        M.y=extr_fin;
        M.c=cost;
        v[i].x=M.x;
        v[i].y=M.y;
        v[i].c=M.c;
    }

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

    for(i=1;i<=n;i++)L[i]=i;
    for(i=1;i<=m;i++)v[i].sem=false;

    k=0;
    suma=0;
    i=1;

    int nrmuchii=0;

    while(k<n && i<=m)
    {
        vfx=v[i].x;
        vfy=v[i].y;

        if(L[vfx]!=L[vfy])
        {
            k++;
            suma=suma+v[i].c;
            varf=L[vfy];
            w=L[vfx];
            v[i].sem=true;
            nrmuchii++;

            for(j=1;j<=n;j++)
                if(L[j]==varf)L[j]=w;
        }

        i=i+1;
    }

    fout<<suma<<'\n';
    fout<<nrmuchii<<'\n';

    for(i=1;i<=m;i++)
        if(v[i].sem==true)fout<<v[i].x<<' '<<v[i].y<<'\n';

    return 0;
}