#include <iostream>
#include <vector>
#include <fstream>
#include <utility>
#include <algorithm>

using namespace std;

#define MAX_NODURI 200005
#define MAX_MUCHII 400005

int N, M;
vector<int> graf[MAX_NODURI];
vector< pair<int, pair<int, int> > > muchii;
int tata[MAX_NODURI];
int grad[MAX_NODURI];
vector<pair<int, int> > raspuns;

int get_tata(int nod)
{
    if(tata[nod] == nod) return nod;
    tata[nod] = get_tata(tata[nod]);
    return tata[nod];
}

void uneste(int nod1, int nod2)
{
    int t1 = get_tata(nod1);
    int t2 = get_tata(nod2);
    //if(grad[t1] == grad[t2]) grad[t1] ++;
    //else
    if(grad[t1] >= grad[t2])
    {
        grad[t1] += grad[t2];
        tata[t2] = t1;
    }
    else
    {
        grad[t2] += grad[t1];
        tata[t1] = t2;
    }
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>N>>M;
    for(int i = 0; i < M; i++)
    {
        int x, y, c;
        f>>x>>y>>c;
        muchii.push_back(make_pair(c, make_pair(x, y)));
    }

    for(int i = 1; i <= N; i++)
    {
        tata[i] = i;
        grad[i] = 1;
    }

    sort(muchii.begin(), muchii.begin() + muchii.size());

    int cost_total = 0;

    for(int i = 0; i < muchii.size(); i++)
    {
        int x, y, c;
        c = muchii[i].first;
        x = muchii[i].second.first;
        y = muchii[i].second.second;
        if(get_tata(x) != get_tata(y))
        {
            uneste(x, y);
            raspuns.push_back(make_pair(x, y));
            cost_total += c;
        }
    }
    g<<cost_total<<"\n"<<raspuns.size()<<"\n";
    for(int i = 0; i < raspuns.size(); i++)
    {
        g<<raspuns[i].first<<" "<<raspuns[i].second<<"\n";
    }

    return 0;
}