#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int NMAX = 200001, MMAX =400001;
int n, m, nrM, T[NMAX];
long long costMin;
struct muchie
{
    int i, j, c;
}M[MMAX];
vector<pair<int, int>> sol;
bool comp(const muchie &a, const muchie &b)
{
    return a.c < b.c;
}
void citire()
{
    int k;
    f >> n >> m;
    for(k = 1; k <= m; k++)
        f >> M[k].i >> M[k].j >> M[k].c;
}
int Find(int i)
{
    if(T[i] == 0) return i;
    return T[i] = Find(T[i]);
}
void Kruskal()
{
    int ci, cj, k;
    sort(M + 1, M + m + 1, comp);
    for(k = 1; k <= m; k++)
    {
        ci = Find(M[k].i), cj = Find(M[k].j);
        if(ci != cj)
        {
            T[ci] = cj;
            costMin += M[k].c;
            nrM++;
            sol.push_back({M[k].i, M[k].j});
            if(nrM == n - 1) break;
        }
    }
    g << costMin << '\n' << nrM << '\n';
    for(const auto &x : sol)
        g << x.first << ' ' << x.second << '\n';
}
int main()
{
    citire();
    Kruskal();
    f.close();
    g.close();
    return 0;
}