#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] += grad[t2];
        tata[t2] = tata[t1];
    }
    else
    {
        grad[t2] += grad[t1];
        tata[t1] = tata[t2];
    }
}

int main()
{
    ifstream f("kruskal.in");
    ofstream g("kruskal.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(tata[x] != tata[y])
        {
            uneste(x, y);
            raspuns.push_back(make_pair(x, y));
            cost_total += c;
        }
    }
    g<<cost_total<<endl<<raspuns.size()<<endl;
    for(int i = 0; i < raspuns.size(); i++)
    {
        g<<raspuns[i].first<<" "<<raspuns[i].second<<endl;
    }

    return 0;
}