#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,i,x,y,c,s;
struct muchie{
int x,y,c,ok;}v[400001],aux;
ifstream f("apm.in");
ofstream g("apm.out");
void poz(int p,int u,int &k)
{
    int i,j,di,dj,aux1;
    di=0;dj=-1;
    i=p;j=u;
    while(i<j)
    {
        if(v[i].c>v[j].c)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            aux1=di;
            di=-dj;
            dj=-aux1;
        }
        i=i+di;
        j=j+dj;
    }
    k=i;

}
void quick(int p,int u)
{
    int k;
    if(p<u)
    {
        poz(p,u,k);
        quick(p,k-1);
        quick(k+1,u);
    }
}
bool comp(muchie i,muchie j)
{
    return (i.c<j.c);
}
void kruskal()
{
    int L[200001],et1,et2,j,nr;
    for(i=1;i<=n;i++)
        L[i]=i;
    i=1;
    while(nr<n-1&&i<=m)
    {
        if(L[v[i].x]!=L[v[i].y])
        {
            v[i].ok=1;
            s+=v[i].c;
            nr++;
             //g<<s<<endl;
            et1=L[v[i].x];
            et2=L[v[i].y];
            for(j=1;j<=n;j++)
                if(L[j]==et2)
                L[j]=et1;
        }
        i++;
    }
    g<<s<<endl;
    g<<nr<<endl;
    for(i=1;i<=m;i++)
        if(v[i].ok==1)
    {
        g<<v[i].y<<" "<<v[i].x<<endl;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    quick(1,m);
    kruskal();
    return 0;
}