#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
using namespace std;

struct graf
{
    int x,y,cost;
};

ifstream fin("apm.in");
ofstream fout("apm.out");

graf mm1[400005],muchii[200005];
int n,m,tata[200005],suma,nr;

inline void Citire()
{
    int i,z,w,c;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        {
            fin>>z>>w>>c;
            mm1[i].x=z;
            mm1[i].y=w;
            mm1[i].cost=c;
            tata[i]=i;
        }
}

inline int cmp(graf const A,graf const B)
{
    return A.cost<B.cost;
}

inline void Union(int x,int y)
{
    tata[y]=x;
}

inline int Find(int x)
{
    int z,w;
    z=x;
    while (tata[x]!=x)
        x=tata[x];
    while (tata[z]!=z)
        {
            w=tata[z];
            tata[z]=x;
            z=w;
        }
    return x;
}

inline void Kruskal()
{
    int i,z,w;
    graf k;
    sort(mm1+1,mm1+m+1,cmp);
    for (i=1;i<=m;i++)
        {
            k=mm1[i];
            z=Find(k.x);
            w=Find(k.y);
            if (z!=w)
                {
                    nr++;
                    Union(z,w);
                    muchii[nr].x=k.x;
                    muchii[nr].y=k.y;
                    //fout<<k.x<<" "<<k.y<<"\n";
                    suma+=k.cost;
                }
        }
}

inline void Afisare()
{
    int i;
    fout<<suma<<"\n";
    fout<<nr<<"\n";
    for (i=1;i<=nr;i++)
        fout<<muchii[i].x<<" "<<muchii[i].y<<"\n";
}

int main()
{
    Citire();
    Kruskal();
    Afisare();
    return 0;
}