#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{int x,y,c;

}u[200001];
int n,m,ct=0,t[200001],h[200001],sol[200001];
int compare(muchii a,muchii b)
{
    return (a.c<b.c);
}
int muchie(int X,int Y)
{
    int r1,r2,x1,y1,C;
    r1=X;
    r2=Y;
    while(r1!=t[r1])r1=t[r1];
    while(r2!=t[r2])r2=t[r2];
    if(r1==r2)return 0;
    while(t[X]!=r1)
    {
        x1=t[X];
        t[X]=r1;
        X=x1;
    }
    while(t[Y]!=r2)
    {
        y1=t[Y];
        t[Y]=r2;
        Y=y1;
    }
    if(h[r1]>h[r2])
    {
        t[r2]=r1;C=r1;
    }
    else{t[r1]=r2;C=r2;}
    if(h[r1]==h[r2])h[C]++;
    return 1;
}
void kruskal()
{int k,i;
    k=0;
    i=1;
    while(k<n-1)
    {
        if(muchie(u[i].x,u[i].y))
        {
            ct+=u[i].c;
            sol[++k]=i;
        }
        i++;
    }
}
int main()
{  int i;
   f>>n>>m;
   for(i=1;i<=n;i++)
   {
       h[i]=1;
       t[i]=i;
   }
   for(i=1;i<=m;i++)
   {
       f>>u[i].x>>u[i].y>>u[i].c;
   }
   sort(u+1,u+m+1,compare);
   kruskal();
   g<<ct<<'\n';
   g<<n-1<<'\n';
   for(i=1;i<n;i++)
    g<<u[sol[i]].y<<" "<<u[sol[i]].x<<'\n';
    return 0;
}