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

using namespace std;
const int NMAX = 200001,
          MMAX = 400001;

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

int n, m, nm, cost, T[NMAX];
vector<pair<int, int>> sol;

struct muchie
{
    int x, y, c;
    bool operator<(const muchie &B) const
    {
        return (c < B.c);
    }
} mu[MMAX];

void citire()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
        f >> mu[i].x >> mu[i].y >> mu[i].c;
}

int Find(int i)
{
    if(!T[i]) return i;
    return T[i] = Find(T[i]);
}

inline void Union(int rx, int ry)
{
    T[ry] = rx;
}

void kruskal()
{
    sort(mu + 1, mu + m + 1);
    //
    for(int i = 1; i <= m; i++)
    {
        int rx = Find(mu[i].x),
            ry = Find(mu[i].y);
        if(rx != ry)
        {
            Union(rx, ry);
            cost += mu[i].c;
            sol.push_back({mu[i].x, mu[i].y});
            if(++nm == n - 1) break;
        }
    }
    //
    g << cost << '\n' << n - 1 << '\n';
    for(const auto &x : sol)
        g << x.first << ' ' << x.second << '\n';
}

int main()
{
    citire();
    kruskal();
    f.close();
    g.close();
    return 0;
}