#include <bits/stdc++.h>

using namespace std;
int N, M;
const int Nmax = 666013;
vector<pair<int, pair<int,int> > > edges;
vector<pair<int,int> > sol;
int daddy[Nmax], rang[Nmax];

int whos_ur_daddy(int k)
{
    if(daddy[k] != k)
        daddy[k] = whos_ur_daddy(daddy[k]);
    return daddy[k];
}

void pairUp(int from, int to)
{
    daddy[daddy[from]] = daddy[to];
}

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

    cin.sync_with_stdio(false);

    cin >> N  >> M;
    for(int i = 1; i <= M; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({c,{a,b}});
    }
    sort(edges.begin(), edges.end());

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

    int total = 0;

    for(auto it : edges) {
        int from = it.second.first;
        int to = it.second.second;

        if(whos_ur_daddy(from) == whos_ur_daddy(to))
            continue;
        pairUp(whos_ur_daddy(from), whos_ur_daddy(to));
        total += it.first;
        sol.emplace_back(from, to);
    }

    cout << total << "\n" << sol.size() << "\n";

    for(auto it : sol)
        cout << it.first << " " << it.second << "\n";

    return 0;
}