/// APM
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define NMax 200001
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x, y, c;
};

muchie G[2*NMax];

int n, m;
int rang[NMax], root[NMax], rootx, rooty;
int cost;
vector<pair<int, int> > ans;

bool cmp(muchie x, muchie y)
{
    return x.c < y.c;
}

int find_root(int x)
{
    while(x != root[x])
        x =  root[x];
    return x;
}

int main()
{
    f >> n >> m;
    /// citesc toate muchiile cu costurile lor
    for(int i =  1; i <= m; ++i)
        f >> G[i].x >> G[i].y >> G[i].c;


    /// sortez muchiile in functie de cost
    sort(G + 1, G + m + 1, cmp);
    /// fol paduri de multimi disjuncte si initializez fiecare mod ca fiind intr-o componenta diferita
    for(int i = 1; i <= n; ++i)/// declar padurea
    {
        rang[i] = 1;
        root[i] = i;
    }
    /// parcurg toate muchiile
    for(int i = 1; i <= m; ++i)
    {
        rootx = find_root(G[i].x);
        rooty = find_root(G[i].y);

        if(rootx != rooty) /// verific daca sunt in comp diferite
        {
            cost += G[i].c; /// adaug la solutie
            ans.push_back(make_pair(G[i].x, G[i].y));
            if(rang[rootx] > rang[rooty])
            {
                rang[rootx] += rang[rooty];
                root[rooty] = rootx;
            }
            else
            {
                rang[rooty] += rang[rootx];
                root[rootx] = rooty;
            }
        }
    }

    g << cost << '\n' << ans.size() << '\n';

    for(int i = 0; i < ans.size(); ++i)
        g << ans[i].first << " " << ans[i].second << '\n';

    return 0;
}