#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 400005
using namespace std;

struct edge{
    int x, y, w;
};

edge edges[nmax];

void get_data (int &n, int &m){
    ifstream fin ("apm.in");
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> edges[i].x >> edges[i].y >> edges[i].w;
}

int find_root (int x, int v[]){
    if (v[x] < 0)   return x;
    v[x] = find_root (v[x], v);
}

void quick_union (int x, int y, int v[]){
    if (v[x] < v[y]){
        v[x] += v[y];
        v[y] = x;
    }
    else{
        v[y] += v[x];
        v[x] = y;
    }
}

bool cmp (edge x, edge y){
    return x.w < y.w;
}

void print_data (int value, vector <pair<int, int> > msp_edges){
    ofstream fout ("apm.out");
    fout << value << "\n" << msp_edges.size() << "\n";
    for (auto x : msp_edges)
        fout << x.first << " " << x.second << "\n";
}

void solve (int n, int m, int value){
    vector < pair<int, int> > msp_edges;
    int v[nmax];
    for (int i = 0; i <= n; i++)
        v[i] = -1;
    sort (edges + 1, edges + m + 1, cmp);
    int j = 0, i = 0;
    while (j != n-1){
        i++;
        int a = find_root (edges[i].x, v);
        int b = find_root (edges[i].y, v);
        if (a != b){
            quick_union (a, b, v);
            value += edges[i].w;
            msp_edges.push_back(make_pair(edges[i].x, edges[i].y));
            j++;
        }
    }
    print_data (value, msp_edges);
}

int main(){
    int n, m, value = 0;
    get_data (n, m);
    solve (n, m, value);
    return 0;
}