#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 5;
int TT[N]; ///vectorul de tati
int RG[N]; ///h subarb cu rad in i
long long costmin = 0;
int n, m;

struct edge
{
    int x, y, c;
};
vector <edge> graph;
vector <pair<int,int>>ans;

struct
{
    bool operator()(edge A, edge B)
    {
        return A.c < B.c;
    }
} cmp;

int find_root(int node)
{
    while(TT[node] != 0)
        node = TT[node];
    return node;
}

int unite(int node_x, int node_y)
{
    node_x = find_root(node_x);
    node_y = find_root(node_y);

    if(node_x == node_y) return 0;

    if(RG[node_x] < RG[node_y])
        swap(node_x, node_y);

    TT[node_y] = node_x;
    RG[node_x] += RG[node_y];

    return 1;
}

main()
{
    in >> n >> m;

    while(m--)
    {
        edge M;
        in >> M.x >> M.y >> M.c;
        graph.push_back(M);
    }

    sort(graph.begin(), graph.end(), cmp);

    for(size_t i = 0; i < graph.size() && ans.size() < n - 1; i++)
        if(unite(graph[i].x,graph[i].y) != 0)
        {
            costmin += graph[i].c;
            ans.push_back({graph[i].x, graph[i].y});
        }

    out << costmin << '\n' << n - 1 << '\n';

    for(size_t i = 0; i < ans.size(); i++)
        out << ans[i].first << ' ' << ans[i].second << '\n';
}