#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int n,mu,t[200003],k,ct,ad[200003],ind;

struct Muchie
{
    int a,b,c;
}m[400003],sol[400003];

bool cmp(Muchie x12,Muchie y12)
{
    return x12.c<y12.c;
}
int Root(int p)
{
    int q=p;
    while(q!=t[q])q=t[q];
    while(p!=t[p])
    {
        int aux=t[p];
        t[p]=q;
        p=aux;
    }
    return q;
}
void Unite(int p,int q)
{
    if(ad[p]>ad[q])t[q]=p;
    else t[p]=q;

    if(ad[p]==ad[q])ad[q]++;
}
int main()
{
    f>>n>>mu;
    for(int i=1;i<=mu;++i)
    {
        f>>m[i].a>>m[i].b>>m[i].c;
        t[i]=i;
    }
    sort(m+1,m+mu+1,cmp);
//    for(int i=1;i<=mu;++i)g<<m[i].c<<" ";
    ind=1;
    while(k<n-1)
    {
        int x=Root(m[ind].a);
        int y=Root(m[ind].b);
        if(x!=y)
        {
            k++;ct+=m[ind].c;
            sol[k]=m[ind];
            Unite(x,y);
        }
        ind++;
    }
    g<<ct<<'\n'<<k<<'\n';
    for(int i=1;i<=k;++i)
    {
        g<<sol[i].b<<" "<<sol[i].a;
        g<<'\n';
    }
}