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

using namespace std;

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

vector< pair<int, int> > g[200001];
int d[200001]; // dist de la i la un nod din arbore = d[i]
int cine[200001]; // cine mi-a dat aceasta distanta minima?
bool adaugat[200001]; // daca e adaugat, pretty ez

void add_la_tree(int nod){
    d[nod] = 0;
    adaugat[nod] = 1;
    for(const pair<int, int> &x : g[nod]){
        if(d[x.first] > x.second){
            d[x.first] = x.second;
            cine[x.first] = nod;
        }
    }
}

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

    int n, m; in >> n >> m;

    for(int i = 0; i < m; i++){
        int x, y, z; in >> x >> y >> z;
        g[x].push_back( mkp(y, z) );
        g[y].push_back( mkp(x, z) );
    }

    for(int i = 0; i <= n; i++) d[i] = INT_MAX;
    add_la_tree(1);

    int sum = 0;
    vector< pair<int, int> > mch;
    for(int it = 2; it <= n; it++){
        int pmin = -1;
        for(int i = 1; i <= n; i++){
            if(adaugat[i]) continue;
            if(pmin == -1 || d[i] < d[pmin]) pmin = i;
        }
        sum += d[pmin];
        mch.push_back( mkp( pmin, cine[pmin] ) );

        add_la_tree(pmin);
    }

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

    return 0;
}