#include <bits/stdc++.h>
#define NMAX 200005
#define MMAX 400005

using namespace std;

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

struct elem
{
    int x, y, cost;

    bool operator<(const elem &x) const
    {
        return cost < x.cost;
    }
};

int n, m, t[NMAX];
vector <pair <int, int>> ans;
elem muchii[MMAX];

void init()
{
    for(int i = 1; i <= n; i++)
        t[i] = i;
}

int radacina(int a)
{
    if(t[a] == a)
        return a;
    return t[a] = radacina(t[a]);
}

void leaga(int a, int b)
{
    t[a] = t[b];
}

int main()
{
    f >> n >> m;

    init();
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        f >> x >> y >> cost;
        muchii[i]= {x, y, cost};
    }

    sort(muchii + 1, muchii + 1 + m);

    int cost = 0;
    for(int i = 1; i <= m; i++)
    {
        int radx = radacina(muchii[i].x);
        int rady = radacina(muchii[i].y);
        if(radx != rady)
        {
            cost += muchii[i].cost;
            ans.push_back(make_pair(muchii[i].x, muchii[i].y));
            leaga(radx, rady);
        }
    }

    g << cost << "\n" << n - 1 << "\n";
    for(vector <pair <int, int>> :: iterator it = ans.begin(); it != ans.end(); it++)
        g << it -> first << " " << it -> second << "\n";


    return 0;
}