#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int T[200008];
int root(int nod)
{
    int nodi=nod;
    while(T[nodi]>0)
        nodi=T[nodi];
    return nodi;
}
void unire(int nod1,int nod2)
{
    T[nod1]=nod2;
}
struct muchie
{
    int x,y,cst;
}mc;
bool cmp(muchie a,muchie b)
{
    return a.cst<b.cst;
}
vector<muchie> M;
int main()
{
    int n,m,i,cost,k;
    FILE *f,*g;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&mc.x,&mc.y,&mc.cst);
        M.push_back(mc);
    } 
    fclose(f);
    sort(M.begin(),M.end(),cmp);
    cost=0;
    k=1;
    for( i=0;i<M.size()&&k<=n-1;i++)
       if(root(M[i].x)!=root(M[i].y))
       {
           unire(M[i].x,M[i].y);
           cost=cost+M[i].cst;
           k++;
       }
    fprintf(g,"%d\n%d\n",cost,n-1);
    for(i=1;i<=n;i++)
        if(T[i]!=0)
           fprintf(g,"%d %d\n",i,T[i]);
    return 0;
}