#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

vector<int> parent;

void make_set(int v)
{
    parent[v] = v;
}

int find_set(int v)
{
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b)
{
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

struct Edge
{
    int u, v, weight;
    bool operator<(Edge const& other)
    {
        return weight < other.weight;
    }
};

int n, m;
vector<Edge> edges;

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        fin >> x >> y >> w;
        edges.push_back({x, y, w});
    }
    int cost = 0;
    vector<Edge> result;
    parent.resize(n);
    for (int i = 0; i < n; i++)
        make_set(i + 1);

    sort(edges.begin(), edges.end());

    for (Edge e : edges)
    {
        if (find_set(e.u) != find_set(e.v))
        {
            cost += e.weight;
            e.weight = 10000;
            result.push_back(e);
            union_sets(e.u, e.v);
        }
    }
    fout << cost << '\n' << n - 1<< '\n';
    for (Edge e : result)
        fout << e.u << ' ' << e.v << '\n';
    return 0;
}