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

using namespace std;

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

struct lat{
    int x;
    int y;
    int cost;
}a[100];

int n,m;
int b[100];
int ales;
int cu;
int costt;
int c[100];

bool cmp(lat i, lat j){
    return i.cost < j.cost;
}

void citire(){
    fin >>n >> m;
    for (int i = 1; i <= m; i++){
        int c,d,f;
        fin >> c >> d >> f;
        if(c > d){
            a[i].x = d;
            a[i].y = c;
            a[i].cost = f;
        }
            else {
            a[i].x = c;
            a[i].y = d;
            a[i].cost = f;
            }
    }
    sort(a + 1, a + m + 1, cmp);
    for(int i = 1; i <= n; i++)
        b[i] = i;
}

void schimb(int y,int x){
    for(int i = 1; i <= n; i++){
        if(b[i] == x)b[i] = y;
    }
}

void rez(){
    while(ales < n - 1){
        cu++;
        if(b[a[cu].x] != b[a[cu].y]){
            costt += a[cu].cost;
            schimb(b[a[cu].x], b[a[cu].y]);
            ales++;
            c[++c[0]] = cu;
        }
    }
}

int main()
{
    citire();
    rez();
    fout << costt;
    fout << '\n' << c[0] << '\n';
    for (int i = 1; i <= c[0]; i++){
        fout << a[c[i]].x << ' ' << a[c[i]].y << '\n';
    }
    return 0;
}