#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>pq;
vector<int>radacina(200005);
vector<pair<int, int>>result;
int tata(int v)
{
    if(radacina[v] == 0)
        return v;
    else
        radacina[v] = tata(radacina[v]);
}

void uneste(int x , int y)
{
    int tx = tata(x);
    int ty = tata(y);
    radacina[ty] = tx;
}
int kruskal()
{
    int nrmuchii = 0, cost = 0;
    while(nrmuchii < n-1)
    {
        auto pr = pq.top();
        pq.pop();

        int x = pr.second.first;
        int y = pr.second.second;

        if(tata(x) != tata(y))
        {
            nrmuchii ++;
            cost += pr.first;
            uneste(x, y);
            result.push_back({x, y});
        }
    }

    return cost;
}
int main()
{

    fin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        pq.push({c, {x, y}});
    }

    fout << kruskal() << "\n" << n - 1 << "\n";
    for(auto r : result)
    {
        fout << r.first << " " << r.second << "\n";
    }
    return 0;
}