#include <fstream>
#include <vector>
#define DIMM 400010
#define DIMN 200010
#define INF 1000000000
using namespace std;

vector<pair< int, int > > L[DIMN];
int d[DIMN], f[DIMN], t[DIMN];
pair<int, int> s[DIMN];
///d[i] = distanta minima de la nodul i la unul dintre nodurile
///din APM deja format
///f[i] = 1 pentru nodurile puse deja in apm
///t[i] = acel nod din apm spre care de la nodul i este distanta minima
int n, m, i, sol, x, y, cost, minim, k, j, p;
int main () {
    ifstream fin ("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>cost;
        L[x].push_back( make_pair(y, cost) );
        L[y].push_back( make_pair(x, cost) );
    }

    d[1] = 0;
    for (i=2;i<=n;i++)
        d[i] = INF;
    for (i=1;i<=n;i++) {
        /// calculez minimul din d, pentru elemente nemarcate
        minim = INF;
        for (j=1;j<=n;j++)
            if (d[j] < minim && f[j] == 0) {
                minim = d[j];
                k = j;
            }
        /// nodul k este cel ales in apm la acest pas
        /// muchia k, t[k] o punem la apm
        if (i != 1) {
            s[++p].first = k;
            s[p].second = t[k];
            sol += d[k]; /// e de fapt costul muchiei k,t[k]
        }

        f[k] = 1;
        for (int j=0;j<L[k].size();j++) {
            int vec = L[k][j].first;
            int cst = L[k][j].second;
            if (f[vec] == 0 && d[vec] > cst) {
                d[vec] = cst;
                t[vec] = k;
            }

        }

    }
    fout<<sol<<"\n"<<n-1<<"\n";
    for (i=1;i<n;i++)
        fout<<s[i].first<<" "<<s[i].second<<"\n";
    return 0;
}