#include<iostream>
#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int NMAX = 50000;
int grp[NMAX],a[NMAX],b[NMAX],c[NMAX];
int n,m,suma,ind[NMAX];
vector<int> v;

int grupa(int i)
{
    if (grp[i] == i) return i;
    grp[i] = grupa(grp[i]);
    return grp[i];
}
void reunion(int i,int j)
{
    grp[grupa(i)] = grupa(j);
}

bool compare(int i,int j)
{
    return(c[i] < c[j]);
}

int main()
{
     f>>n>>m;

    for(int i = 1;i <= m;++i)
    {
        f>>a[i]>>b[i]>>c[i];
        ind[i] = i;
    }
    for(int i = 1;i <= n; ++i)
        grp[i] = i;

    sort(ind + 1,ind + m + 1,compare);

    for(int i = 1;i <= m; ++i)
    {
        if (grupa(a[ind[i]])!= grupa(b[ind[i]]))
        {   suma+=c[ind[i]];
            reunion(a[ind[i]],b[ind[i]]);
            v.push_back(ind[i]);
        }
    }

    g<<suma<<'\n'<<n-1<<'\n';

    for(int i = 0;i < n - 1; ++i)
        g<<b[v[i]]<<" "<<a[v[i]]<<'\n';

    return 0;
}