#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int NMAX = 2e5 + 10;
vector < pair < int, pair < int, int > > > Edges;
vector < pair < int, int > > APM;
int N, M, Fathers[NMAX];

int getFather(int x)
{
    if(Fathers[x] == x)
        return x;
    Fathers[x] = getFather(Fathers[x]);
    return Fathers[x];
}

inline bool checkOrder(pair < int, pair < int, int > > A, pair < int, pair < int, int > > B)
{
    return A.first < B.first;
}

int main()
{
    in >> N >> M;
    int x, y, c;
    for(int i = 1; i <= M; i++)
        in >> x >> y >> c, Edges.push_back({c, {x, y}});
    for(int i = 1; i <= N; i++)
        Fathers[i] = i;
    sort(Edges.begin(), Edges.end(), checkOrder);
    // for(pair < int, pair < int, int > > it : Edges)
    //     cout << it.second.first << ' ' << it.second.second << '\n';
    int cost = 0;
    for(pair < int, pair < int, int > > it : Edges)
    {
        if(getFather(it.second.first) == getFather(it.second.second))
            continue;
        
        cost += it.first;
        Fathers[Fathers[it.second.second]] = Fathers[it.second.first];
        APM.push_back({it.second.first, it.second.second});
    }
    out << cost << '\n' << N-1 << '\n';
    for(pair < int, int > it : APM)
        out << it.first << ' ' << it.second << '\n';
    return 0;
}