#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct tot{
int c1,x1,y1;
}v[400001],z[400001];

int p[400001],r[400001];

int find_root(int k)
{
    if(k!=p[k])
        p[k]=find_root(p[k]);
        return p[k];
}
bool comp(struct tot a, struct tot b)
{
    return a.c1<b.c1;
}
int main()
{
    int n,m,x,nr=0,y,cost=0,i,j,xroot,yroot,c;
 f>>n>>m;
 for(i=1;i<=m;i++)
 {
     f>>x>>y>>c;
    v[i].x1=x;
    v[i].y1=y;
    v[i].c1=c;

 }
// for(i=1;i<m;i++)
   // for(j=i+1;j<=m;j++)
  //  if(v[i].c1>v[j].c1)
  //  swap(v[i],v[j]);
sort (v+1,v+m+1,comp);
    // for(i=1;i<=m;i++)
     //    g<<v[i].x1<<" "<<v[i].y1<<" "<<v[i].c1<<endl;

for(i=1;i<=n;i++)
{
    p[i]=i;
    r[i]=0;
}
for(i=1;i<=m;i++)
{
    xroot=find_root(v[i].x1);
    yroot=find_root(v[i].y1);
    if(xroot!=yroot)
    {
        nr++;
        z[nr]=v[i];
        cost = cost + v[i].c1;
        if(xroot>yroot)
            p[yroot]=xroot;
        else
            if(xroot<yroot)
            p[xroot]=yroot;
        else
        {
            p[yroot]=xroot;
            r[xroot]++;
        }
    }
}
g<<cost<<endl;
g<<n-1<<endl;
for(i=1;i<=nr;i++)
    g<<z[i].x1<<" "<<z[i].y1<<endl;

    return 0;
}