/**
- sortez muchiile crescator dupa cost
- traversez muchiile in ordine crescatoare
  daca capetele muchiei curente sunt in componente
  conexe diferite aleg aceasta muchie, unind totodata
  cele doua componente conexe.

  Faptul ca 2 noduri sunt deja in aceeasi componenta
  conexa face ca adaugarea unei muchii intre ele sa
  produca un ciclu (ele aveau inainte un lant intre ele
  si acum l-as inchide)
**/

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

using namespace std;

ifstream fin  ("apm.in");
ofstream fout ("apm.out");
int t[200010], S[200010];
int a, b, ra, rb, n, m, i, sol, alese;

int rad(int x) { /// returnreaza radacina arborelui in care este nodul x
    while(t[x] > 0)
        x = t[x];
    return x;
}

pair< int, pair<int, int> > v[400010];

int main (){
    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>v[i].second.first>>v[i].second.second>>v[i].first;
    sort(v+1, v+m+1);

    for (i=1;i<=n;i++)
        t[i] = -1;

    for (i=1;i<=m;i++) {
        a = v[i].second.first;
        b = v[i].second.second;

        ra = rad(a);
        rb = rad(b);

        /// daca la unire pastrez mereu ca radacina
        /// pe cea a arborelui cu mai multe noduri
        /// este demonstrat ca mereu inaltimea
        /// ramane de ordin log n
        if (ra != rb) {
            if (-t[ra] > -t[rb]) {
                /// a ramane radacina
                t[ra] += t[rb];
                t[rb] = ra;
            } else {
                t[rb] += t[ra];
                t[ra] = rb;
            }
            sol += v[i].first;

            /// optimizare
            alese++;
            S[alese] = i;
            if (alese == n-1)
                break;
        }
    }
    fout<<sol<<"\n"<<n-1<<"\n";
    for (i=1;i<=alese;i++)
        fout<<v[ S[i] ].second.first<<" "<<v[ S[i] ].second.second<<"\n";
    return 0;
}