#include <cstdio>
#include <algorithm>
#include <vector>
#define NMAX 400005

using namespace std;

int n,m,i,j,x,y,c,t;
long long S;
int tata[NMAX/2],poz[NMAX];
vector<int>sol;
struct muchie
{
    int x,y,c;
}muc[NMAX];

bool cmp(int p,int r)
{
    return(muc[p].c < muc[r].c);
}

int mul(int nod)
{
    if(tata[nod] == 0) return nod;
    tata[nod]=mul(tata[nod]);
    return tata[nod];
}

void reuneste(int a,int b)
{
    tata[mul(a)]=mul(b);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        muc[i].x=x;muc[i].y=y;muc[i].c=c;
        poz[i]=i;
    }
    sort(poz+1,poz+m+1,cmp);
    for(t=1;t<=m;++t)
    {
        i=poz[t];
        x=muc[i].x;y=muc[i].y;
        if(mul(x) != mul(y))
        {
            reuneste(mul(x),mul(y));
            S += muc[i].c;
            sol.push_back(i);
        }
    }

    printf("%lld\n%d\n",S,n-1);
    for(i=0;i<sol.size();++i)
        printf("%d %d\n",muc[sol[i]].x,muc[sol[i]].y);
    return 0;
}