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

#define NMAX 200005

using namespace std;

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

struct Muchie
{
    int x, y;
    bool operator<(const Muchie& a) const
    {
        return x < a.x;
    }
};

int n, m;
vector<pair<int, int>> l[NMAX];
vector<pair<int, Muchie>> v;
vector<Muchie> rez;
int tata[NMAX], sz[NMAX];
int i, j;

int find(int);
void unite(int, int);

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

    for (i = 1; i <= n; ++i)
        tata[i] = i, sz[i] = 1;
    
    sort(v.begin(), v.end());

    int counter = 0; int suma = 0;
    for (i = 0; counter < n - 1; ++i)
    {
        int x = v[i].second.x;
        int y = v[i].second.y;
        int c = v[i].first;
        if (find(x) != find(y))
        {
            unite(x, y);
            suma += c;
            rez.push_back({ x, y });
            counter++;
        }
    }

    fout << suma << '\n';
    fout << rez.size() << '\n';
    for (auto it : rez)
        fout << it.x << ' ' << it.y << '\n';
    return 0;
}

int find(int node)
{
    if (tata[node] == node)
        return node;
    return tata[node] = find(tata[node]);
}

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

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

    tata[y] = x;
    sz[x] += sz[y];
}