#include<stdio.h>
#include<vector>

#define INF (2 << 29) - 1

using namespace std;

int nrNoduri;
vector< pair<int, int> > listeAdiacenta[1008];

int costMin = 0;
int tata[1006];


void citire();
void genAPM(int startNode);
void afisare();

int main() {
	citire();

    genAPM(0);

	afisare();
	return 0;
}

void citire() {
	FILE* fin = fopen("apm.in", "r");
    int nrMuchii, nod1, nod2, cost;
    int i;
    fscanf(fin, "%d%d", &nrNoduri, &nrMuchii);

    for (i = 0; i < nrNoduri; i++){
        fscanf(fin, "%d%d%d", &nod1, &nod2, &cost);
        listeAdiacenta[nod1 - 1].push_back(make_pair(nod2 - 1, cost));
        listeAdiacenta[nod2 - 1].push_back(make_pair(nod1 - 1, cost));
    }

	fclose(fin);
}

void genAPM(int startNode){
    bool selected[1008];
    int cmin[1008];
    int i;
    int nod;
    int next, nextCost;
    for (i = 0; i < nrNoduri; i++){
        cmin[i] = INF;
        tata[i] = startNode;
        selected[i] = false;
    }
    for (i = 0; i < listeAdiacenta[startNode].size(); i++){
        cmin[listeAdiacenta[startNode][i].first] = listeAdiacenta[startNode][i].second;
    }
    selected[startNode] = true;
    tata[startNode] = -1;
    while(true){
        nod = 0;
        for (i = 0; i < nrNoduri; i++){
            if (cmin[i] < cmin[nod]){
                nod = i;
            }
        }
        if (cmin[nod] == INF){
            break;
        }
        selected[nod] = true;
        costMin += cmin[nod];
        cmin[nod] = INF;
        for (i = 0; i < listeAdiacenta[nod].size(); i++){
            next = listeAdiacenta[nod][i].first;
            nextCost = listeAdiacenta[nod][i].second;
            if (!selected[next] &&
                nextCost < cmin[next]){
                cmin[next] = nextCost;
                tata[next] = nod;
            }
        }
    }
}

void afisare() {
	FILE* fout = fopen("apm.out", "w");
    int i;
    fprintf(fout, "%d\n", costMin);
    fprintf(fout, "%d\n", nrNoduri-1);
    for (i = 1; i < nrNoduri; i++){
        fprintf(fout, "%d %d\n", i+1, tata[i]+1);
    }

	fclose(fout);
}