#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

class graf {

protected:
    int noduri, muchii;
    vector < vector < int >> adiacenta;

public:
    // Constructor cu matrice de adiacenta data
    graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

    // Constructor fara matrice de adiacenta, se cu initalizeaza una goala
    graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

    vector < int > bfs(int);
    int dfs();

};

class graf_neorientat : public graf{
private:
    void dfsbiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
    void dfsCriticalConnections(int tata, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);

public:
    graf_neorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_neorientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat&);

    vector < string > biconex();

    vector < vector < int >> criticalConnections();
};

class graf_orientat : public graf{
private:
    void dfsCtc(int, vector < int >&, vector < int >&, stack < int >&, int&, vector < string >&, unordered_set < int >&);
    void dfsSortaret(int, vector < int >&, vector < int >&);

public:
    graf_orientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_orientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_orientat&);

    vector < string > ctc();

    vector < int > sortaret();
};

class graf_neorientat_ponderat : public graf_neorientat {
    // Matrice de adianceta care contine si costurile
    vector< vector< pair< int, int >>> adiacentap;
public:
    graf_neorientat_ponderat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf_neorientat(listaAdiacenta, noduri, muchii) {};
    graf_neorientat_ponderat(int noduri, int muchii): adiacentap(noduri+1), graf_neorientat(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat_ponderat&);

    vector< vector< int >> apm(vector< vector< int >>& much, ostream&out){
        vector< int > tata(noduri + 1);
        vector< vector < int >> rasp;

        sort(much.begin(), much.end(), [] (vector<int> a, vector<int> b) {
             return a[2] < b[2];
        });

        int i = 0, j = 0;
        int s=0;

        for(int i=1; i<tata.size(); i++){
            tata[i]=i;
        }

        while(i < this->noduri - 1 && j < much.size()){
            int aux1 = much[j][0], aux2 = much[j][1];
            int tata1 = aux1, tata2 = aux2;
            while(tata1 != tata[tata1]){
                tata1 = tata[tata1];
            }
            while(tata2 != tata[tata2]){
                tata2 = tata[tata2];
            }
            if(tata1 != tata2){
                s+=much[j][2];
                tata[aux1] = tata[aux2];
                rasp.push_back({aux1, aux2});
                i++;
            }
            j++;
        }
        out<<s<<'\n'<<this->noduri-1<<'\n';
        return rasp;
    }
};

void apmDriver() {
    // Citire
    ifstream in ("apm.in");
    ofstream out("apm.out");

    int n, m;
    in >> n >> m;
    graf_neorientat_ponderat x(n, m);
    vector< vector< int >> much;
    for (int i = 0; i < m; i++) {
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        much.push_back({aux1, aux2, aux3});
    }
    // Afisare
    vector< vector< int >> v = x.apm(much, out);
    for(auto i:v){
        out<<i[0]<<" "<<i[1]<<"\n";
    }

}

int main() {
    // Se apeleaza functia corespunzatoare problemei
    apmDriver();
    return 0;
}