#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn = 200005;
vector <pair <int, int> > vec[maxn];
vector <pair <int, int> > sol;
struct muchie
{
    int p, q, cost;
};
vector <muchie> muchii;

int F[maxn];

int rad(int x)
{
    if(F[x] < 0)
        return x;
    return rad(F[x]);
}

inline bool test(int x, int y)
{
    return rad(x) == rad(y);
}

void add(int x, int y)
{
    int a = rad(x);
    int b = rad(y);
    if(F[a] > F[b])
    {
        F[b] += F[a];
        F[a] = y;
    }
    else
    {
        F[a] += F[b];
        F[b] = x;
    }
}

inline bool cmp(muchie a, muchie b)
{
    if(a.cost != b.cost)
        return a.cost < b.cost;
    return 0;
}

muchie make_muchie(int a, int b, int c)
{
    muchie aux;
    aux.p = a;
    aux.q = b;
    aux.cost = c;
    return aux;
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i++)
        F[i] = -1;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        muchii.push_back(make_muchie(x, y, c));
        vec[x].push_back(make_pair(y, c));
        vec[y].push_back(make_pair(x, c));
    }
    sort(muchii.begin(), muchii.end(), cmp);
    int s = 0;
    for(auto it : muchii)
    {
        int x = it.p;
        int y = it.q;
        if(test(x, y) == 0)
        {
            s = s + it.cost;
            sol.push_back(make_pair(x, y));
            add(x, y);
        }
    }
    out << s << "\n" << n - 1 << "\n";
    for(auto it : sol)
        out << it.first << " " << it.second << "\n";
    return 0;
}