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

///complexitate mare O(n*m) cred

pair<pair<int, int>, int>muchii[200005];
void citire(int &n, int &m)
{
    ifstream fin("apm.in");
    fin >> n >> m;
    int i;
    //cout << "citire\n";
    for(i = 0; i < m; i++)
        {
            int a, b, c;
            fin >> a >> b >> c;
            muchii[i] = make_pair(make_pair(a, b), c);
            //cout << muchii[i].first.first << " " << muchii[i].first.second << " " << muchii[i].second << "\n";
        }
    //cout << "\n-----------------------\n";
    fin.close();
}

bool cmp(pair<pair<int, int>, int> a, pair <pair<int, int>, int> b)
{
    return (a.second < b.second);
}
void sortare(int m)
{
    sort(muchii, muchii + m, cmp);
}

pair<int, int> x[200005];
void kruskal(int n, int m, int viz[], int &cost_total, int &k)
{
    int i;
    cost_total = 0;
    k = 0;
    for(i = 1; i <= n; i++)
        viz[i] = i;

    ///obligatoriu sortarea
    sortare(m);
    //cout << "din kruskal\n";
    //for(i = 0; i < m; i++)
        //{
            //cout << muchii[i].first.first << " " << muchii[i].first.second << " " << muchii[i].second << "\n";
        //}
    //cout << "\n-----------------------\n";

    for(i = 0; i < m; i++)
    {
        if(viz[muchii[i].first.first] != viz[muchii[i].first.second])
        {

            x[k] = make_pair(muchii[i].first.first, muchii[i].first.second);
            //cout << x[k].first << " " << x[k].second << "\n";
            k++;
            cost_total += muchii[i].second;
            int a = viz[muchii[i].first.second];

            for(int j = 1; j <= n; j++) ///reuniunea
                if(viz[j] == a)
                    viz[j] = viz[muchii[i].first.first];
            if(k == n - 1)
                break;
        }
    }
}
int main()
{
    int n, m, k, cost_total;

    citire(n, m);

    int viz[n + 1];
    kruskal(n, m, viz, cost_total, k);

    ofstream fout("apm.out");
    fout << cost_total << "\n";
    fout << k << "\n";
    for(int i = 0; i < k; i++)
        fout << x[i].first << " " << x[i].second << "\n";
    return 0;
}