#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

ofstream out("apm.out");

struct padure
{
    int n;
     vector<int> tat;
    vector<int> rang;

    padure(int a): n(a), tat(a+1), rang(a+1, 1)
    {
        for(int i = 1; i <= n; ++i)
            tat[i] = i;
    }

    int find_tat(int nod)
    {
        if(tat[nod] == nod)
            return nod;
        else
        {
            int tata = find_tat(tat[nod]);
            tat[nod] = tata;
            return tata;
        }
    }

    bool find_r(int x, int y)
    {
        if(find_tat(x) == find_tat(y))
            return true;
        else
            return false;
    }

    void union_nod(int x, int y)
    {
        int tx = find_tat(x);
        int ty = find_tat(y);
        if(rang[tx] < rang[ty])
        {
            tat[tx] = ty;
            rang[ty] += rang[tx];
        }
        else
        {
            tat[ty] = tx;
            rang[tx] += rang[ty];
        }
    }

    void afis()
    {
        for(int i = 0; i < n; ++i)
            cout << tat[i] << ' ';
        cout << endl;
    }

};

int main()
{
    ifstream in("apm.in");
    in.exceptions(in.failbit);

    int n, m;
    in >> n >> m;
    padure P(n);
    vector < pair<int, pair<int, int> > > graf;
    vector <pair<int, int> > rez;

    for(int i = 0; i < m; ++i)
    {
        int cost, x, y;
        in >> x >> y >> cost;
        graf.push_back({cost, {x, y} });
        graf.push_back({cost, {y, x} });

    }
    sort(graf.begin(), graf.end());

    int sum = 0;
    for(int i = 0; i < graf.size(); ++i)
    {
        int x = graf[i].second.first;
        int y = graf[i].second.second;
        if(P.find_r(x, y) == false)
        {
            rez.push_back({x, y});
            sum += graf[i].first;
            P.union_nod(x, y);
        }
    }
    out << sum << "\n";
    out << n-1 << "\n";
    for(int i = 0; i < rez.size(); ++i)
        out << rez[i].first << ' ' << rez[i].second << "\n";


    in.close();
    out.close();
}