#include <algorithm>
#include <iostream>
#include <vector>
#include <stdio.h>

#define pb push_back
#define nMax 400005

using namespace std;

int x[nMax], y[nMax], c[nMax];
int ind[nMax];
int gr[nMax];
int m, n;
int sum;
//vector <int> sol;
int ir;
int sol[nMax];

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

int grupa(int i)
{
    if(gr[i] == i)
        return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}

void reuniune(int i, int j)
{
    gr[grupa(i)] = grupa(j);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for(int i=1; i<=m;++i)
    {
        scanf("%d %d %d\n", &x[i], &y[i], &c[i]);
        ind[i] = i;
    }

    for(int i=0;i<=n;++i)
        gr[i] = i;

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

    for(int i=1;i<=m;++i)
    {
        if(grupa(x[ind[i]]) != grupa(y[ind[i]]))
        {
            sum+=c[ind[i]];
            reuniune(x[ind[i]], y[ind[i]]);
            sol[ir++]= ind[i];
        }
    }

    printf("%d \n", sum);
    printf("%d \n", n-1);

    for(int i=0;i<n-1;++i)
    printf("%d %d\n", x[sol[i]], y[sol[i]]);

    return 0;
}