#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int N = 200001;
const int M = 2*N;

int n,m,a[N],v[N],o[N],nv;

struct muchie
{
    int x,y,c;
}s[N];

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

int radacina(int i)
{
    if(!a[i])
        return i;
    a[i]=radacina(a[i]);
    return a[i];
}

void unire(int i,int j)
{
    a[radacina(i)]=radacina(j);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i,APM=0;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&s[i].x,&s[i].y,&s[i].c);
        o[i]=i;
    }
    sort(o+1,o+m+1,cmp);
    for(i=1;i<=m;i++)
        if(radacina(s[o[i]].x)!=radacina(s[o[i]].y))
        {
            APM+=s[o[i]].c;
            unire(s[o[i]].x,s[o[i]].y);
            v[++nv]=o[i];
        }
    printf("%d\n%d\n",APM,n-1);
    for(i=1;i<n;i++)
        printf("%d %d\n",s[v[i]].y,s[v[i]].x);
    return 0;
}