#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

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

#define N 200001


int main(){
    
    int n, m;
    fin >> n >> m;

    vector<vector<pair<int,int>>> l(n+1);
    vector<int> cost(n+1, INT_MAX), arbore;
    vector < pair<int, int> >edges;
    vector<bool> isArbore(n + 1, 0);

    while (m--) {
        int a, b, c;
        fin >> a >> b >> c;
        
        l[a].push_back({ b,c });
        l[b].push_back({ a,c });
    }

    
    int size = 1;
    arbore.push_back(1); // adaug 1 in arbore
    cost[1] = 0;
    isArbore[1] = 1;
    int costTotal = 0;

    while (size != n){

        int minimEdge, x, y;
        minimEdge = INT_MAX;

        for (int i : arbore)
            for (auto prs:l[i])
                if (isArbore[prs.first] == 0 && prs.second < minimEdge){
                    
                    minimEdge = prs.second;
                    x = i;
                    y = prs.first;
                }

        edges.push_back({ x, y });
        size++;

        isArbore[y] = 1;
        arbore.push_back(y);
        costTotal += minimEdge;
    }

    
    fout << costTotal << "\n";
    fout << n-1 << "\n";

    for (auto i : edges)
        fout << i.first << " " << i.second << "\n";
}