#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
priority_queue <pair<int,pair<int,int> > > q;
int vTati[200005],cost=0,m,n;
void citire()
{
    int aux1,aux2,aux3;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&aux1,&aux2,&aux3);
        q.push(make_pair(-aux3,make_pair(aux1,aux2)));
    }
}
int getTata(int nod)
{
    while(vTati[nod]!=nod)
    {
        nod=vTati[nod];
    }
    return nod;
}
void apm()
{
    for(int i=1;i<=n;i++)
        vTati[i]=i;

    int n1,n2,c;
    while(!q.empty())
    {
        c=-q.top().first;
        n1=q.top().second.first;
        n2=q.top().second.second;
        q.pop();
        if(getTata(n1)!=getTata(n2))
        {
            vTati[getTata(n2)]=getTata(n1);
            cost+=c;
        }
    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    apm();
    printf("%d\n%d\n",cost,n-1);
    for(int i=1;i<=n;i++)
    {
        if(vTati[i]!=i)
            printf("%d %d\n",i,vTati[i]);
    }
    return 0;
}