#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <algorithm>
#define NMAX 400001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,a,b,c,RG[NMAX],TT[NMAX],Total=0,k=0;
pair <int,int> P[NMAX];
struct Muchii
{
    int x;
    int y;
    int c;
}U[NMAX];
void Citire()
{
    f>>n;
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>U[i].x;
        f>>U[i].y;
        f>>U[i].c;
    }
}
bool Compara(Muchii a, Muchii b)
{
    return a.c < b.c;
}
int Gasit(int Nod)
{
    while(Nod!=TT[Nod])
        Nod=TT[Nod];
    return Nod;
}
void Unire(int x,int y)
{
    if(RG[x]<RG[y])
        TT[x]=y;
    if(RG[x]>RG[y])
        TT[y]=x;
    if(RG[x]==RG[y])
    {
        TT[x]=y;
        RG[y]++;
    }
}
void Rezolvare()
{
    for(int i=1;i<=m;i++)
    {
        if(Gasit(U[i].x)!=Gasit(U[i].y))
        {
            Unire(Gasit(U[i].x),Gasit(U[i].y));
            k++;
            P[k].first=U[i].x;
            P[k].second=U[i].y;
            Total=Total+U[i].c;
        }
    }
}
void Afisare()
{
    g<<Total<<'\n';
    g<<k<<'\n';
    for(int i=1;i<=k;i++)
        g<<P[i].second<<' '<<P[i].first<<'\n';
}
int main()
{
    Citire();
    sort(U+1,U+m+1,Compara);
    for(int i=1;i<=n;i++)
    {
        TT[i]=i;
        RG[i]=1;
    }
    Rezolvare();
    Afisare();

    return 0;
}