#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 = 500000 + 1;

int n,m,suma,k[NMAX],grp[NMAX],a[NMAX],b[NMAX],c[NMAX];

vector<int> vec;

bool compare(int i,int j)
{
    return(c[i] < c[j]);
}
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);
}


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

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

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

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

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

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

    return 0;
}