#include<algorithm>
#include<cstdio>
#include<vector>
#define inf 0x3f3f3f
#define NMax 200005
using namespace std;

int tata[NMax],C[NMax],H[2*NMax],Pos[NMax],L;
vector<pair<int,int> > V[NMax],VSol;

void update_costs (int nod)
{
    vector<pair<int,int> >::iterator it;
    for (it=V[nod].begin(); it!=V[nod].end(); ++it)
        if (C[it->first] > it->second)
        {
            C[it->first] = it->second;
            tata[it->first] = nod;
        }
}

void up_heap (int nod)
{
    while (nod/2 && C[H[nod]]<C[H[nod/2]])
    {
        swap(H[nod],H[nod/2]);
        swap(Pos[H[nod]],Pos[H[nod/2]]);
        nod/=2;
    }
}

void down_heap (int nod)
{
    int mini=0;
    while (1)
    {
        mini=nod;
        if (2*nod<=L && C[H[mini]]>C[H[2*nod]])
            mini=2*nod;
        if (2*nod+1<=L && C[H[mini]]>C[H[2*nod+1]])
            mini=2*nod+1;
        if (mini==nod) return;
        swap(H[mini],H[nod]);
        swap(Pos[H[mini]],Pos[H[nod]]);
        nod=mini;
    }
}

int root_heap ()
{
    int root=H[1];
    Pos[root]=0;
    H[1]=H[L];
    Pos[H[1]]=1;
    L--;
    down_heap(1);
    return root;
}

int main ()
{
    int x,y,cost,i,M,N,costT=0;
    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,&cost);
        V[x].push_back(make_pair(y,cost));
        V[y].push_back(make_pair(x,cost));
    }
    for (i=2; i<=N; i++)
        C[i]=inf;
    update_costs(1);
    for (i=2; i<=N; i++)
    {
        H[++L]=i;
        Pos[i]=L;
    }
    for (i=1; i<N; i++)
    {
        int crt=root_heap();
        update_costs(crt);
        vector<pair<int,int> >::iterator it;
        for (it=V[crt].begin(); it!=V[crt].end(); ++it)
            if (Pos[it->first])
                up_heap(Pos[it->first]);
        costT+=C[crt];
        VSol.push_back(make_pair(crt,tata[crt]));
    }
    printf("%d\n",costT);
    printf("%d\n",N-1);
    for (i=0; i<N-1; i++)
        printf("%d %d\n",VSol[i].first,VSol[i].second);
    return 0;
}