#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMax = 200005;
int GR[NMax];
int niv[NMax];
int N, M;

int Find(int nod)
{
    if(nod != GR[nod])
        GR[nod] = Find(GR[nod]);

    return GR[nod];
}

void Join(int x, int y)
{
    if(niv[x] == niv[y])
    {
        ++niv[x];
        GR[y] = x;
    }

    else
        if(niv[x] > niv[y])
    {
        GR[y] = x;
    }

    else
        GR[x] = y;
}

struct muchie
{
    int x, y, c;
}G[2*NMax];

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

vector < pair < int,  int > > rez;

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

    scanf("%d%d", &N,&M);

    for(int i=1; i<=N; ++i)
        GR[i] = i;

    for(int i=1; i<=M; ++i)
    {
        scanf("%d%d%d", &G[i].x, &G[i].y, &G[i].c);
    }

    sort(G+1, G+M+1, cmp);

    int cst = 0;
    int m = 0;

    for(int i=1; m < N-1; ++i)
    {
        if(Find(G[i].x) != Find(G[i].y))
        {
            cst += G[i].c;
            rez.push_back({G[i].x,G[i].y});
            Join(Find(G[i].x), Find(G[i].y));
            ++m;
        }

    }

    cout << cst << "\n";
    cout << m << "\n";

    for(int i=0; i<rez.size(); ++i)
        cout << rez[i].first << " " << rez[i].second << "\n";
    return 0;
}