#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define Dmax 400005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

pair <int, int > p[Dmax];
int k=0,n,m,Total=0,TT[Dmax],RG[Dmax];

struct Muchie{
    int x;int y; int cost;
}v[Dmax];

bool Compare(Muchie a, Muchie b)
{

    return a.cost < b.cost;
}

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,Compare);


    for(int i=1;i<=n;i++)
    {
        TT[i]=i;
        RG[i]=1;

    }

}

int Find(int Nod)
{
    while(TT[Nod] != Nod)
        Nod = TT[Nod];
    return Nod;
}

void Unire(int x, int y)
{
    if(RG[x] < RG[y])
        TT[x]=y;
    else if(RG[x] > RG[y])
        TT[y]=x;
    else
    {
        TT[x] = y;
        RG[y]++;
    }
}
void Kruskal()
{
    for(int i=1; i<=m; i++)
    {
        int aux1,aux2;
        aux1=Find(v[i].x);
        aux2=Find(v[i].y);
        if(aux1!=aux2)
        {
            Unire(aux1,aux2);
            p[++k]=make_pair(v[i].x,v[i].y);
            Total += v[i].cost;
        }
    }


}
int main()
{
    citire();
    Kruskal();
    g<<Total<<"\n";
    g<<k<<"\n";
    for(int i=1;i<=k;i++)
        g<<p[i].first<<" "<<p[i].second<<"\n";

    return 0;
}