#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;

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

// implementare cu Kruskal

int f[200001];
int s[200001];

int sum = 0;
vector< pair<int, int> > mch;

int find_father(int x){
    if( f[x] == x ) return x;
    f[x] = find_father( f[x] );
    return f[x];
}

void merge(int a, int b, int c){
    int fa = find_father(a);
    int fb = find_father(b);

    if(fa == fb) return; // is deja merged :)
    
    mch.push_back( make_pair(a, b) );
    sum += c;

    if(s[a] > s[b]){
        f[fb] = fa;
        s[fa] += s[fb]; 
    }else{
        f[fa] = fb;
        s[fb] += s[fa];
    }
}

struct muchie{
    int a, b, c;

    bool operator<(const muchie &b) const {
        return c < b.c;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, m; in >> n >> m;
    muchie v[m];

    for(int i = 0; i < m; i++) in >> v[i].a >> v[i].b >> v[i].c;

    sort(v + 0, v + m);

    for(int i = 0; i <= n; i++){ f[i] = i; s[i] = 1; }

    for(int i = 0; i < m; i++) merge( v[i].a, v[i].b, v[i].c );

    out << sum << '\n' << mch.size() << '\n';
    for(const pair<int, int> &x : mch) cout << x.first << " " << x.second << '\n';


    return 0;
}