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

using namespace std;

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

int n, m;

struct muchii{
    int x,y;
    int c;
} M[1000008];

int T[100008];
int H[100008];
int C[100008];

int lgRez = 0;
int Rez[100008];

int cost;

int Find(int nod);
void Union(int t1, int t2);

bool compare(muchii a, muchii b){
    return a.c < b.c;
}

int main(){

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> M[i].x >> M[i].y >> M[i].c;
    }

    sort(M + 1, M + m + 1,  compare);

    for(int i = 1; i <= m; i++){

        int t1 = Find(M[i].x);
        int t2 = Find(M[i].y);

        if(t1 !=  t2){
            Union(t1, t2);
            cost = C[t1] + C[t2] + M[i].c;
            C[t1] = C[t2] = cost;
            Rez[++lgRez] = i;
        }

    }

    fout << cost << '\n';
    fout << lgRez << '\n';
    for(int i = 1; i <= lgRez; i++)
        fout << M[Rez[i]].x << ' ' << M[Rez[i]].y << '\n';

  return 0;

}

int Find(int nod){

    int y = nod;
    while(T[nod] != 0){
        nod = T[nod];
    }

    while(T[y] != 0){
        int aux = T[y];
        T[y] = nod;
        y = aux;
    }

    return nod;

}

void Union(int t1, int t2){

    if(H[t1] > H[t2])
        T[t2] = t1;
    else if(H[t1] < H[t2])
        T[t1] = t2;
    else{
        T[t1] = t2;
        H[t2]++;
    }


}