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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

vector<int> parent, rank_set;

void make_set(int node)
{
    parent[node] = node;
    rank_set[node] = 0;
}

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

void union_set(int a, int b)
{
    a = find_set(a);
    b = find_set(b);
    if (a != b)
    {
        if (rank_set[a] < rank_set[b])
            swap(a, b);
        parent[b] = a;
        if (rank_set[a] == rank_set[b])
            rank_set[a]++;
    }
}

struct Edge
{
    int x, y, c;
    bool operator<(Edge b)
    {
        return c < b.c;
    }
};

int main()
{
    int n, m, cost = 0;
    f >> n >> m;
    vector<Edge> edges(m + 1);
    vector<Edge> result;
    parent.resize(n + 1);
    rank_set.resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        f >> edges[i].x >> edges[i].y >> edges[i].c;
    }

    for (int i = 1; i <= n; i++)
        make_set(i);
    sort(edges.begin(),edges.end());
    for (auto edge : edges)
    {
        if (find_set(edge.x) != find_set(edge.y))
        {
            cost += edge.c;
            result.push_back(edge);
            union_set(edge.x, edge.y);
        }
    }

    g << cost << endl;
    g << result.size() << endl;
    for (int i = 0; i < result.size(); i++)
        g << result[i].y << " " << result[i].x << endl;
    return 0;
}