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

#define infile "apm.in"
#define outfile "apm.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);

struct edge{
    int x;
    int y;
    int cost;
};

bool comp(edge x, edge y)
{
    return x.cost < y.cost;
}

int n, m;
int x, y, cost;
vector<edge> graph;
int compConex[200005];
int height[200005];
int costApm;
vector< pair<int, int> > muchi;


int find_root(int x)
{
    int root = 0;
    for(root=x; root!=compConex[root]; root=compConex[root]);

    for(int y=x; y!=compConex[y]; y=compConex[y]){
        compConex[y] = root;
    }
    return root;
}

void combine(int x, int y)
{
    int root_x = find_root(x);
    int root_y = find_root(y);
    if(height[root_x] > height[root_y]){
        compConex[root_y] = root_x;
    }
    if(height[root_x] < height[root_y]){
        compConex[root_x] = root_y;
    }
    if(height[root_x] == height[root_y]){
        compConex[root_y] = root_x;
        height[root_x]++;
    }
}

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

    for(int i=1; i<=m; i++){
        in >> x >> y >> cost;
        graph.push_back({x, y, cost});
    }

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

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

    for(int i=0; muchi.size()<n-1; i++){
        int x = graph[i].x;
        int y = graph[i].y;
        int cost = graph[i].cost;
        if(find_root(x) == find_root(y)){
            continue;
        }
        costApm += cost;
        combine(x, y);
        muchi.push_back({x, y});
    }


    out << costApm << '\n';
    out << muchi.size() << '\n';
    for(int i=0; i<muchi.size(); i++){
        out << muchi[i].first << ' ' << muchi[i].second << '\n';
    }

    return 0;
}