#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

int n, m, suma;

struct amp{
    int x, y, c;
};;

struct comp {
    bool operator()(amp const& a, amp const& b) {
        return a.c > b.c;
    }
};

struct lat{
    int index, cost;
    bool fol;
};
vector<vector<lat> > L(400000);
vector<amp> rezultat;
priority_queue <int, vector<amp>, comp> coada;

void cauta(int x, int y){
    for(int i = 0; i < L[x].size(); ++i)
    if(L[x][i].index == y){
        L[x][i].fol = 1;
        break;
    }
}

int main()
{
    in>>n>>m;

    for(int i=1; i<=m; ++i){
        int x, y, c;
        lat muchie;

        in>>x>>y>>c;
        muchie.index = y;
        muchie.cost = c;

        L[x].push_back(muchie);

        muchie.index = x;
        L[y].push_back(muchie);
    }

    for(int i = 1; i <= n - 1; ++i){
        for(int j = 0; j < L[i].size(); ++j){
            amp muchie;
            muchie.x = i;
            muchie.y = L[i][j].index;
            muchie.c = L[i][j].cost;
            if(!L[i][j].fol) coada.push(muchie);
            L[i][j].fol = 1;

            cauta(L[i][j].index, i);
        }

        amp fr = coada.top();
        rezultat.push_back(fr);
        suma += fr.c;
        coada.pop();

    }
    out<<suma<<'\n'<<n-1<<'\n';
    for(int i = 0; i < rezultat.size(); ++i)
        out<<rezultat[i].x<<" "<<rezultat[i].y<<'\n';

    in.close();
    out.close();
    return 0;
}