#include<iostream>
#include<fstream>
#include<vector>
#include <algorithm> 
using namespace std;
int n,m;
struct muchie{
    int x;
    int y;
    int pond;
};
vector<muchie>muchii;
bool cmp(muchie a, muchie b)
{
    return a.pond < b.pond;
}
void scrie(vector<muchie> muchii)
{
    int m = muchii.size();
    for (int i = 0; i < m; i++)
        cout << muchii[i].x << " " << muchii[i].y << " " << muchii[i].pond << "\n";
    cout << "\n";
}
/*
void sort(vector<muchie> &muchii)
{
    int m = muchii.size();
    for (int i = 0; i < m - 1; i++)
        for (int j = i+1; j < m; j++)
        {
            if (muchii[i].pond>muchii[j].pond)
            {
                muchie aux = muchii[i];
                muchii[i] = muchii[j];
                muchii[j] = aux;
                //scrie(muchii);
            }
        }
}*/
int main()
{
    ifstream f("apm.in");
    f >> n>> m;
    int x, y,p;
    for (int i = 0; i < m; i++)
    {
        f >> x >> y >> p;
        muchie m;
        m.x = x;
        m.y = y;
        m.pond = p;
        muchii.push_back(m);
    }
    sort(muchii.begin(),muchii.end(),cmp);
    //for (int i = 0; i < m; i++)
    //  cout << muchii[i].x<<" "<< muchii[i].y <<" "<< muchii[i].pond<<"\n";
 
    vector<muchie> apm_muchii;
    int *fathers = new int[n];
    for (int i = 1; i <= n; i++)
        fathers[i] = i;
    int cost = 0;
    for (int i = 0; i < muchii.size() && apm_muchii.size()<n-1; i++)
    {
        muchie mu = muchii[i];
        if (fathers[mu.x] != fathers[mu.y])
        {
            apm_muchii.push_back(mu);
            cost += mu.pond;
            for (int j = 1; j <= n; j++)
                if (fathers[j] == fathers[mu.x])
                    fathers[j] = fathers[mu.y];
        }
    }
    //cout << "\n";
    //cout <<"Cost:"<< cost << "\n";
    //scrie(apm_muchii);
    ofstream g("apm.out");
    g << cost << "\n";
    g << apm_muchii.size()<<"\n";
    for (int i = 0; i < apm_muchii.size(); i++)
        g << apm_muchii[i].x << " " << apm_muchii[i].y << "\n";
    f.close();
    g.close();
    return 0;
}