#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define file_in "apm.in"
#define file_out "apm.out"

#define nmax 494984

int n,m;
int x[nmax];
int y[nmax];
int c[nmax];
int ind[nmax];
int sol[nmax];
int tata[nmax];

void citire()
{
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d %d",&n,&m);
    int i;
    for (i=1;i<=m;++i)
    {
        scanf("%d %d %d", &x[i], &y[i], &c[i]);
        ind[i]=i;
    }

}

int father(int x)
{
    if (tata[x]!=x)
         tata[x]=father(tata[x]);
    return tata[x];
}

void unite(int i, int j)
{
    tata[i]=j;
}

int cmp(int a, int b)
{
    return c[a]<c[b];
}

void solve()
{
    int i,nr,cost_apm=0,t1,t2;
    sort(ind+1,ind+m+1,cmp);
    nr=0;
    for (i=1;i<=n;++i) tata[i]=i;
    for (i=1;i<=m;++i)
    {
        t1=father(x[i]);
        t2=father(y[i]);

        if (t1!=t2)
        {
            unite(t1,t2);
            cost_apm+=c[ind[i]];
            sol[++nr]=ind[i];
        }
    }

    printf("%d\n", cost_apm);
    printf("%d\n", n-1);
    for (i=1;i<=nr;++i)
         printf("%d %d\n", x[sol[i]],y[sol[i]]);


}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}