#include <fstream>
#define MMAX 400000
#define NMAX 200000
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct ura{

    int n1, n2, c;
}v[MMAX+1];

int sef[NMAX+1], viz[MMAX+1];

int sef_suprem(int x)
{
    if (sef[x]==x)
        return x;
    return sef_suprem(sef[x]);
}

void unire(int a, int b)
{
    int sef_a, sef_b;
    sef_a = sef_suprem(a);
    sef_b = sef_suprem(b);
    sef[sef_a] = sef_b;
}

bool sortare(ura a,ura b)
{
    return (a.c < b.c);
}

int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
        cin>>v[i].n1>>v[i].n2>>v[i].c;
    sort(v+1, v+m+1, sortare);
    for (int i=1; i<=n; i++)
        sef[i] = i;
    int nr=0;
    int s = 0;
    for (int i=1; i<=m && nr<n-1; i++)
        if (sef_suprem(v[i].n1) != sef_suprem(v[i].n2))
    {
        unire(v[i].n1, v[i].n2);
        nr++;
        s+=v[i].c;
        viz[i]=1;
    }

    cout<<s<<"\n"<<n-1<<"\n";
    for (int i=1;i<=m;i++)
        if (viz[i]==1)
            cout<<v[i].n1<<" "<<v[i].n2<<"\n";
    return 0;
}