#include <cstdio>
#include <climits>
#include<vector>
#define inf INT_MAX/2
#define nmax 200100

using namespace std;

vector<pair<int,int> > lv[nmax];

int n,m,nh=0;
int t[nmax],d[nmax],h1[nmax],h2[nmax],iheap[nmax];
char viz[nmax];

void push(int val,int nod)
{
    ++nh;
    h1[nh]=val;
    h2[nh]=nod;
    iheap[nod]=nh;
    int nodc=nh;
    while(nodc/2 && h1[nodc]<h1[nodc/2])
    {
        swap(h1[nodc],h1[nodc/2]);
        swap(h2[nodc],h2[nodc/2]);
        swap(iheap[h2[nodc]],iheap[h2[nodc/2]]);
        nodc/=2;
    }
}

void pop(int &k,int &cost)
{
    cost=h1[1];k=h2[1];
    iheap[k]=0;
    swap(h1[1],h1[nh]);
    swap(h2[1],h2[nh]);
    nh--;
    iheap[h2[1]]=1;
    int nodc=1,fiu;
    while(1)
    {
        if(nodc>nh)break;
        fiu=2*nodc;
        if(fiu>nh)break;
        if(fiu+1<=nh && h1[fiu]>h1[fiu+1])fiu++;
        if(h1[nodc]<h1[fiu])break;
        swap(h1[nodc],h1[fiu]);
        swap(h2[nodc],h2[fiu]);
        swap(iheap[h2[nodc]],iheap[h2[fiu]]);
        nodc=fiu;
    }
}

void update_heap(int nod,int cost)
{
    int nodc=iheap[nod];
    h1[nodc]=cost;
    while(nodc/2 && h1[nodc]<h1[nodc/2])
    {
        swap(h1[nodc],h1[nodc/2]);
        swap(h2[nodc],h2[nodc/2]);
        swap(iheap[h2[nodc]],iheap[h2[nodc/2]]);
        nodc/=2;
    }

}

int main()
{
    FILE *f=fopen("apm.in","r");
    fscanf(f,"%d%d",&n,&m);
    int i,x,y,c;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        lv[x].push_back(make_pair(y,c));
        lv[y].push_back(make_pair(x,c));
    }
    vector < pair<int,int> >::iterator it;
    d[1]=0;viz[1]=1;
    for(i=2;i<=n;i++)d[i]=inf;
    for(it=lv[1].begin();it!=lv[1].end();it++)
        {
            d[it->first]=it->second;
            t[it->first]=1;
        }
    for(i=2;i<=n;i++)
            push(d[i],i);
    int k,cost,capm=0;
    for(i=2;i<=n;i++)
    {
        pop(k,cost);viz[k]=1;
        capm+=cost;
        for(it=lv[k].begin();it!=lv[k].end();it++)
            if(!viz[it->first]&&it->second < d[it->first])
            {
                d[it->first]=it->second;
                update_heap(it->first,it->second);
                t[it->first]=k;
            }
    }
    f=fopen("apm.out","w");
    fprintf(f,"%d\n%d\n",capm,n-1);
    for(i=1;i<=n;i++)
        if(t[i])fprintf(f,"%d %d\n",i,t[i]);
    return 0;
}