#include <bits/stdc++.h>
#define N_MAX 200000 + 1
using namespace std;

int parent[N_MAX], tree_size[N_MAX];

int find_root(int node)
{
    int root = node;

    while(parent[root])
    {
        root = parent[root];
    }

    int aux = node;

    while(node != root)
    {
        aux = parent[node];
        parent[node] = root;
        node = aux;
    }

    return root;
}


void union_trees(int node_x, int node_y)
{
    int root_x = find_root(node_x);
    int root_y = find_root(node_y);

    if(root_x == root_y) return;

    if(tree_size[root_x] < tree_size[root_y]) swap(root_x, root_y);

    parent[root_y] = root_x;
    tree_size[root_x] += tree_size[root_y];
}


struct Muchie{
    int x, y, cost;
};

vector<Muchie> graph;
int N, M;

vector<pair<int, int>> answer;

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

    fin >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        Muchie m;

        fin >> m.x >> m.y >> m.cost;

        graph.push_back(m);
    }

    sort(graph.begin(), graph.end(), [](Muchie A, Muchie B){
         return A.cost < B.cost;
    });

    int cost = 0;

    for(int i = 0; (i < (int)graph.size()) && ((int)answer.size() != N - 1); ++i)
    {
        if(find_root(graph[i].x) == find_root(graph[i].y)) continue;

        union_trees(graph[i].x, graph[i].y);

        cost += graph[i].cost;

        answer.push_back({graph[i].x, graph[i].y});
    }

    fout << cost << '\n';

    fout << N - 1 << '\n';

    for(pair<int, int>& muchie : answer)
    {
        fout << muchie.first << ' ' << muchie.second << '\n';
    }
}