#include<cstdio>
#include<cmath>
#define NMAX 200200
#include<vector>
#include<algorithm>
using namespace std;
struct gf
{
    int l,r;
};
vector<gf>sol;
vector<gf>v[NMAX];
int cost[NMAX],H[NMAX*2+100],Poz[NMAX],tata[NMAX];
int n,m,i,x,y,c,lg;
void apm(int nod)
{
    vector<gf>::iterator it;
    for(it=v[nod].begin();it!=v[nod].end();++it)
    {
        gf X=*it;
        if (cost[X.l]>X.r) {cost[X.l]=X.r;tata[X.l]=nod;}
    }
}
void pop(int poz)
{
    while (poz>1 && cost[H[poz]]<cost[H[poz/2]])
    {
        swap(H[poz],H[poz/2]);
        swap(Poz[H[poz]],Poz[H[poz/2]]);
        poz=poz/2;
    }
}
void bagaheap(int nod)
{
    H[++lg]=nod;
    Poz[nod]=lg;
    pop(lg);
}
void push(int poz)
{
    while ( (poz*2<=lg && cost[H[poz]]>cost[H[poz*2]])|| (poz*2+1<=lg+1 && cost[H[poz]]>cost[H[poz*2+1]]))
    {
        if (cost[H[poz*2]]<cost[H[poz*2+1]] || poz*2+1>lg)
        {
            swap(H[poz],H[poz*2]);
            swap(Poz[H[poz]],Poz[H[poz*2]]);
            poz=poz*2;
        }
        else
        {
            swap(H[poz],H[poz*2+1]);
            swap(Poz[H[poz]],Poz[H[poz*2+1]]);
            poz=poz*2+1;
        }
    }
}
int Minim()
{
    int Min=H[1];
    swap(H[1],H[lg]);
    swap(Poz[H[1]],Poz[H[lg]]);
    --lg;
    push(1);
    Poz[Min]=0;
    return Min;
}
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);
        gf X; X.l=y,X.r=c;
        v[x].push_back(X);
        X.l=x;X.r=c;
        v[y].push_back(X);
    }
    for (i=2;i<=m;++i) cost[i]=INFINITY;
    cost[1]=0;
    apm(1);
    for (i=2;i<=n;++i)
    {
        bagaheap(i);
    }
    int sum=0;
    for (i=1;i<n;++i)
    {
        int x=Minim();
        apm(x);
        sum+=cost[x];
        gf X;X.l=x;X.r=tata[x];
        sol.push_back(X);
        vector<gf>::iterator it;
        for (it=v[x].begin();it!=v[x].end();++it)
        {
            gf X=*it;
            if (Poz[X.l]!=0) pop(Poz[X.l]);
        }
    }
    printf("%d\n%d\n",sum,n-1);
    vector<gf>::iterator it;
    for (it=sol.begin();it!=sol.end();++it)
    {
        gf X=*it;
        printf("%d %d\n",X.l,X.r);
    }
    return 0;
}