#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t[200001],n,m,rang[200001];
struct muchii
{
    int a,b,cost;
}x[400001],arbore[400001];
void citire()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>x[i].a>>x[i].b>>x[i].cost;
}
int comp(muchii i, muchii j)
{
    return (i.cost<j.cost);
}
void initializare()
{
    int i;
    for(i=1;i<=n;i++)
        t[i]=i;
}
int multime(int nod)
{
    if(t[nod]!=nod)
        t[nod]=multime(t[nod]);
    return t[nod];
}
void unire(int i, int j)
{
    if(rang[i]<rang[j])
            t[i]=j;
    else
        if(rang[i]==rang[j])
        {
            rang[i]++;
            t[i]=j;
        }
        else
            t[j]=i;
}
int main()
{
    int i,atata,btata,s=0,k=0;
    citire();
    sort(x+1,x+m+1,comp);
    initializare();
    for(i=1;i<=m;i++)
    {
        atata=multime(x[i].a);
        btata=multime(x[i].b);
        if(t[atata]!=t[btata])
        {
            s+=x[i].cost;
            unire(atata,btata);
            arbore[++k].a=x[i].a;
            arbore[k].b=x[i].b;

        }
    }
    g<<s<<'\n'<<k<<'\n';
    for(i=1;i<=k;i++)
        g<<arbore[i].a<<" "<<arbore[i].b<<'\n';
    return 0;
}