#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct elem
{
    int x,y,c;
}v[400005],mem[400005];
int n,m,L[200005],rang[200005];
int radacina(int k)
{
    while(L[k]!=k)
        k=L[k];
    return k;
}
bool comp(elem a, elem b)
{
    return a.c<b.c;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1, v+m+1, comp);

    int cnt=0;
    long long ct=0;
     for(int i=1;i<=n;i++)
     {
         L[i]=i;
         rang[i]=1;
     }
     for(int i=1;i<=m;i++)
     {
         int rx=radacina(v[i].x);
         int ry= radacina(v[i].y);

         if(rx!=ry)
         {
             cnt++;
             ct+=v[i].c;
             mem[cnt].x=v[i].x;
             mem[cnt].y=v[i].y;

             if(rang[rx]>rang[ry])
                L[ry]=rx;
             else
             {
                 L[rx]=ry;
                 if(rang[rx]==rang[ry])
                    rang[ry]++;
             }
         }
     }
     g<<ct<<endl<<cnt<<endl;
     for(int i=1;i<=cnt;i++)
        g<<mem[i].x<<" "<<mem[i].y<<'\n';

    return 0;
}