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

using namespace std;

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

const int NMAX = 200000 + 5;
const int MMAX = 400000 + 5;

struct edge
{
    int x;
    int y;
    int cost;

    edge()
    {
        x = 0;
        y = 0;
        cost = 0;
    }

    edge(int _x, int _y)
    {
        x = _x;
        y = _y;
        cost = 0;
    }

    edge(int _x, int _y, int _cost)
    {
        x = _x;
        y = _y;
        cost = _cost;
    }

    bool operator < (const edge &arg) const
    {
        return cost < arg.cost;
    }
};

vector <edge> ans;
edge v[MMAX];
int n, m, sum;
int father[MMAX], rang[NMAX];

int find_root(int x)
{
    if (x != father[x])
        return father[x] = find_root(father[x]);
    return x;
}

void unite(int x, int y)
{
    x = find_root(x);
    y = find_root(y);

    if (rang[x] < rang[y]) swap(x, y);

    father[y] = x;
    rang[x] += rang[y];
}

void init_disjoint()
{
    for (int i = 1; i <= n; ++i)
    {
        father[i] = i;
        rang[i] = 1;
    }
}

void write()
{
    fout << sum << '\n' << ans.size() << '\n';
    for (auto i: ans)
        fout << i.x << " " << i.y << '\n';
}

void read()
{
    int x, y, c;

    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        v[i] = edge(x, y, c);
    }
}

int main()
{
    read();
    init_disjoint();
    sort(v + 1, v + m + 1);

    for (int i = 1; i <= m; ++i)
    {
        int x = v[i].x;
        int y = v[i].y;
        int cost = v[i].cost;

        if (find_root(x) != find_root(y))
        {
            unite(x, y);
            sum += cost;
            ans.push_back(edge(x, y));
        }
    }

    write();

    return 0;
}