#include<stdio.h>
#include<vector>
#define INF 1000001
#define Nmx 200005
#define pb push_back
#define mp make_pair

using namespace std;

int n,m,Heap[Nmx*70],viz[Nmx],pz[Nmx],apm[Nmx],ns,nr,cost[Nmx];
vector< pair<int,int> > G[Nmx];

struct nod
{
    int x,y;
}sol[Nmx];

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].pb(mp(y,c));
        G[y].pb(mp(x,c));
    }
}

void schimb(int x,int y)
{
    int aux=Heap[x];
    Heap[x]=Heap[y];
    Heap[y]=aux;
}

void up_heap(int k)
{
    while(k>1)
    {
        if(cost[Heap[k/2]]<=cost[Heap[k]])
            return ;
        viz[Heap[k/2]]=k;
        viz[Heap[k]]=k/2;
        schimb(k,k/2);
        k=k/2;
    }
}

void downheap(int k)
{
    while(k*2<=nr)
    {
        int p=k*2;
        if(p+1<=nr&&cost[Heap[p+1]]<cost[Heap[p]])
            ++p;
        if(cost[Heap[p]]>cost[Heap[k]])
            return;
        viz[Heap[p]]=k;
        viz[Heap[k]]=p;
        schimb(p,k);
        k=p;
    }
}

void solve()
{
    vector< pair<int,int> > ::iterator it;
    for(int i=1;i<=n;++i)
        cost[i]=INF;
    for(it=G[1].begin();it!=G[1].end();++it)
    {
        cost[it->first]=it->second;
        apm[it->first]=1;
        Heap[++nr]=it->first;
        viz[it->first]=nr;
        up_heap(nr);
    }
    viz[1]=-1;
    int sum=0;
    for(int i=2;i<=n;++i)
    {
        int nod=Heap[1];
        viz[nod]=-1;
        schimb(1,nr);
        viz[Heap[1]]=1;
        Heap[nr--]=0;
        downheap(1);
        sum+=cost[nod];
        int min=INF,pzz=0;
        for(it=G[nod].begin();it!=G[nod].end();++it)
        {
            if(viz[it->first]==-1)
                continue;
            if(!viz[it->first])
            {
                Heap[++nr]=it->first;
                apm[it->first]=nod;
                cost[it->first]=it->second;
                viz[it->first]=nr;
                up_heap(nr);
            }
            else if(it->second<cost[it->first])
            {
                apm[it->first]=nod;
                cost[it->first]=it->second;
                up_heap(viz[it->first]);
            }
        }
        sol[++ns].x=pzz;
        sol[ns].y=nod;
    }
    printf("%d\n%d\n",sum,n-1);
    for(int i=2;i<=n;++i)
        printf("%d %d\n",i,apm[i]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    solve();
    return 0;
}