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

using namespace std;

struct muchie
{
    int n1;
    int n2;
    int c;
};

muchie v[400100];
int T[200100];
int H[200100];
int ales[200100][2];
int cmin=0;

bool crit(muchie a,muchie b)
{ return (a.c<b.c); }

int Arbore(int x)
{
    if (T[x]==0) return x;
    return Arbore(T[x]);
}

int main()
{
    int n,m,i;
    freopen("apm.in","r",stdin);
    ofstream g("apm.out");
    scanf("%d%d",&n,&m);
    for (i=0; i<m; i++)
        scanf("%d%d%d",&v[i].n1,&v[i].n2,&v[i].c);
    sort(v,v+m,crit);

    int nr=0;
    int Cap1,Cap2;
    for (i=0; i<m && nr<n-1; i++)
    {
        Cap1=Arbore(v[i].n1); Cap2=Arbore(v[i].n2);
        if (Cap1 != Cap2)
        {
            cmin+=v[i].c;
            ales[nr][0]=v[i].n1;
            ales[nr++][1]=v[i].n2;
            if (H[Cap1]==H[Cap2])
            {
                ++H[Cap1];
                T[Cap2]=Cap1;
            }
            else if (H[Cap1]>H[Cap2])
                T[Cap2]=Cap1;
            else T[Cap1]=Cap2;
        }
    }

    g<<cmin<<'\n';
    g<<nr<<'\n';
    for (i=0; i<nr; i++)
        g<<ales[i][0]<<' '<<ales[i][1]<<'\n';

    return 0;
}