#include<bits/stdc++.h>
using namespace std;

int n,m,i,j,l,x,y,c,vf,nod,cost;
long long ct;
int d[200005],H[200005],p[200005],t[200005];

vector < pair<int,int> > G[200005];

int inf=2000000000;
struct solutie
{
    int x,y;
};
solutie sol[200005];

ifstream f("apm.in");
ofstream g("apm.out");

void up(int k)
{
    while(k>1 && d[H[k]]<d[H[k/2]])
    {
        swap(H[k],H[k/2]);
        swap(p[H[k]],p[H[k/2]]);
        k=k/2;
    }
}

void down(int k)
{
    int tata=k,fiu=2*k;
    while(fiu<=l)
    {
        if(fiu+1<=l && d[H[fiu]]>d[H[fiu+1]]) fiu++;
        if(d[H[tata]]>d[H[fiu]])
        {
            swap(H[tata],H[fiu]);
            swap(p[H[tata]],p[H[fiu]]);
            tata=fiu;
            fiu=2*tata;
        }
        else fiu=l+1;
    }
}



void creareHeap(int vf)
{
    H[++l]=vf;
    p[vf]=l;
    up(l);
}

int extMin()
{
    int vf=H[1];
    swap(H[1],H[l]);
    swap(p[H[1]],p[H[l]]);
    l--;
    down(1);
    p[vf]=0;
    return vf;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }

    for(i=1;i<=n;i++)
        d[i]=inf;
    d[1]=0;
    t[1]=0;
    for(vector< pair<int,int> >::iterator it=G[1].begin();it<G[1].end();it++)
    {
        d[it->first]=it->second;
        t[it->first]=1;
    }

    for(i=2;i<=n;i++)
        creareHeap(i);

    ct=0;
    for(i=1;i<=n-1;i++)
    {
        vf=extMin();

        for(vector< pair<int,int> >::iterator it=G[vf].begin();it<G[vf].end();it++)
        {
            nod=it->first;
            cost=it->second;
            if(d[nod]>cost)
            {
                d[nod]=cost;
                t[nod]=vf;
            }
        }

        ct+=d[vf];
        sol[i].x=vf;
        sol[i].y=t[vf];

        for(vector< pair<int,int> >::iterator it=G[vf].begin();it<G[vf].end();it++)
        {
            if(p[it->first]!=0) up(p[it->first]);
        }
    }

    g<<ct<<"\n";
    g<<n-1<<"\n";
    for(i=1;i<=n-1;i++)
       g<<sol[i].x<<" "<<sol[i].y<<"\n";

    f.close();
    g.close();
    return 0;
}