#include <bits/stdc++.h>
using namespace std;

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

struct Edge
{
    int u, v, weight;

    Edge(int u, int v, int weight) : u(u), v(v), weight(weight)
    {
    }

    bool operator<(const Edge &other)
    {
        return weight < other.weight;
    }
};

struct DSU
{
    vector<int> parent, sz;

    DSU(int n)
    {
        parent.assign(n + 1, 0);
        sz.assign(n + 1, 1);

        for (int i = 1; i <= n; i++)
            parent[i] = i;
    }

    int find(int a)
    {
        if (parent[a] == a)
            return a;

        return parent[a] = find(parent[a]);
    }

    void unite(int a, int b)
    {
        a = find(a);
        b = find(b);

        if (sz[a] > sz[b])
            swap(a, b);

        parent[a] = b;
    }
};

int n, m, cost;
vector<Edge> edge_list, mst;

void read()
{
    fin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        edge_list.push_back(Edge(x, y, c));
    }
}

void kruskal()
{
    DSU dsu(n);
    sort(edge_list.begin(), edge_list.end());
    for (auto &edge : edge_list)
    {
        if (dsu.find(edge.u) != dsu.find(edge.v))
        {
            mst.push_back(edge);
            cost += edge.weight;
            dsu.unite(edge.u, edge.v);
        }
    }
}
int main()
{
    read();
    kruskal();

    fout << cost << '\n';
    fout << mst.size() << '\n';
    for(auto &edge:mst)
        fout<< edge.v << ' ' << edge.u << '\n';
    return 0;
}