#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int NMAX=200000;

int T[NMAX+1],n,m,cost,Nrm[NMAX],nm;

struct muc
{
    int x,y,c;
}M[NMAX*2+1];

void citire()
{
    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        f>>M[i].x>>M[i].y>>M[i].c;
    }
}

bool comp(muc a,muc b)
{
    return a.c<b.c;
}

int Find(int i)
{
    if (T[i]==0) return i;
    return T[i]=Find(T[i]);
}

void kruskal()
{
    sort(M+1,M+m+1,comp);
    for (int i=1;i<=m;i++)
    {
        int cx,cy;
        cx=Find(M[i].x);
        cy=Find(M[i].y);
        if (cx!=cy)
        {
            Nrm[++nm]=i;
            cost+=M[i].c;
            T[cx]=cy;
            if (nm==n-1) break;
        }
    }
}

void afis()
{
    g<<cost<<'\n'<<nm<<'\n';
    for (int i=1;i<=nm;i++)
    {
        g<<M[Nrm[i]].x<<' '<<M[Nrm[i]].y<<'\n';
    }
}

int main()
{
    citire();
    kruskal();
    afis();
    return 0;
}