//Kruskal
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <int> rez;
struct muchie
{
    int a,b,c;
}m[400002];
int n,t[400002],rang[400002];

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

int rad(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}

void unite(int a, int b)
{
    if(rang[a]==rang[b])
    {
        t[b]=a;
        rang[a]++;
    }
    else
        if(rang[a]>rang[b])
            t[b]=a;
        else t[a]=b;
}
int main()
{
    int nrm,i,x,y,s=0;
    f>>n>>nrm;
    for(i=1;i<=nrm;i++)
    {
        f>>m[i].a>>m[i].b>>m[i].c;
        t[m[i].a]=m[i].a;
        t[m[i].b]=m[i].b;
        rang[m[i].a]=rang[m[i].b]=1;
    }
    sort(m+1,m+nrm+1,comp);

    for(i=1;i<=nrm;i++)
    {
        x=rad(m[i].a);
        y=rad(m[i].b);
        if(x!=y)
        {
            unite(x,y);
            rez.push_back(i);
            s+=m[i].c;
        }
    }
    g<<s<<'\n';
    g<<n-1<<'\n';
    for(i=0;i<rez.size();i++)
    {
        g<<m[rez[i]].a<<' '<<m[rez[i]].b<<'\n';
    }
}