#include <iostream>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int n1;
    int n2;
    int cost;
}v[400005],aux,u[400005];
int p[400005],r[400005];
void quicksort(muchie v[],int l,int r)
{
    int i=l,j=r,p=v[(l+r)/2].cost;
    while(i<=j)
    {
        while(v[i].cost<p)
        i++;
        while(v[j].cost>p)
        j--;
        if(i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            i++;
            j--;
        }
    }
    if(l<j)
    quicksort(v,l,j);
    if(i<r)
    quicksort(v,i,r);
}
int find_root(int k)
{
    while(k!=p[k])
   k=p[k];
    return p[k];
}
int main()
{
    int n,m,x,y,c,xroot,yroot,nr=0;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        v[i].n1=x;
        v[i].n2=y;
        v[i].cost=c;
    }
    quicksort(v,1,m);
    //for(int i=1;i<=m;i++)
   // out<<v[i].n1<<" "<<v[i].n2<<" "<<v[i].cost<<endl;
    for(int i=1;i<=n;i++)
    {   p[i]=i;
        r[i]=0;
    }
    c=0;
    for(int i=1;i<=m;i++)
    {
        xroot=find_root(v[i].n1);
        yroot=find_root(v[i].n2);
        if(xroot!=yroot)
        {
            nr++;
            c=c+v[i].cost;
            u[nr]=v[i];
            if(r[xroot]>r[yroot])
            p[yroot]=xroot;
            else
            if(r[yroot]>r[xroot])
            p[xroot]=yroot;
            else
            {
                p[yroot]=xroot;
                r[xroot]++;
            }
        }
    }
    out<<c<<endl<<nr<<endl;
    for(int i=1;i<=nr;i++)
    out<<u[i].n1<<" "<<u[i].n2<<endl;
    return 0;
}