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

using namespace std;

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

const int Nmax = 200000;
vector <Edge> edges;
vector <Edge> ans;
int x[Nmax + 1];
int cnt[Nmax + 1];

int jump(int node)
{
    if (node == x[node])
    {
        return node;
    }
    return x[node] = jump(x[node]);
}

void unite(int node1, int node2)
{
    int a = jump(node1);
    int b = jump(node2);
    if (a != b)
    {
        if (cnt[a] < cnt[b])
        {
            swap(a, b);
        }
        x[b] = a;
        if (cnt[a] == cnt[b])
        {
            cnt[a]++;
        }
    }
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    for (int i = 1; i <= n; i++)
    {
        x[i] = i;
    }
    sort(edges.begin(), edges.end());
    int cost = 0;
    for (Edge e : edges)
    {
        if (jump(e.u) != jump(e.v))
        {
            cost += e.w;
            ans.push_back(e);
            unite(e.u, e.v);
        }
    }
    fout << cost << "\n";
    fout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
    {
        fout << ans[i].u << " " << ans[i].v << "\n";
    }
    return 0;
}