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

#define VALMAX 100005

using namespace std;

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


vector<int> componente[VALMAX+1];


stack <int> Stiva;
int vizitat[VALMAX + 1];
int vizitatT[VALMAX + 1];


bool comparare_functie(pair< int, pair <int, int > > x, pair<int, pair <int, int> > y)
{
    if(x.second.second == y.second.second){
        return make_pair(x.first,x.second.first) < make_pair(y.first,y.second.first);
    }

    return x.second.second < y.second.second;
}

struct nod{

nod *next;
int cost;
int val;

};

class OrientedGraph{

protected:
    nod *varfuri[VALMAX];
    nod *varfuriT[VALMAX];
    int nrVarfuri;
    int nrMuchii;
    int varfStart;
    int vizitat[VALMAX + 1];
    int vizitatT[VALMAX + 1];
    int drc[VALMAX + 1];
    vector <pair<int, pair < int, int> > > edges;


public:

    int getNrVarfuri(){
        return this->nrVarfuri;
    }

    OrientedGraph(){
        vizitAll();
        //makeDrc0();
    }

    OrientedGraph(int nrV, int nrM): nrVarfuri(nrV), nrMuchii(nrM){
        vizitAll();
        //makeDrc0();
    }

void vizitAll(){
    /*
    for(int i = 1;i<=VALMAX;++i){
        vizitat[i] = 0;
        vizitatT[i] = 0;
    }
    */
}


void citireOrientat(){
    if(!nrVarfuri)fin>>nrVarfuri>>nrMuchii;
/// default behavior
    for(int i = 1;i<=nrMuchii;++i){
        int x, y, cost;
        fin>>x>>y>>cost;
        edges.push_back(make_pair(x, make_pair(y, cost)));
        nod *p = new nod;
        p->val = x;
        p->cost = cost;
        p->next = varfuriT[y];
        varfuriT[y] = p;


        p = new nod;
        p->val = y;
        p->cost = cost;
        p->next = varfuri[x];
        varfuri[x] = p;

    }
}

void afisare(){

    for(int i = 1;i<=nrVarfuri;++i){
        nod *p = varfuri[i];
        cout<<"varf: "<<i<<"...: ";
        while(p){
            cout<<p->val<<" ";
            p = p->next;
        }
        cout<<endl;
    }

}


};

class ComponenteTareConexe: public OrientedGraph{

public:
    ComponenteTareConexe(): OrientedGraph(){}
    ComponenteTareConexe(int nrV, int nrM): OrientedGraph(nrV, nrM){}


void dfs1(int varf){

    vizitat[varf] = 1;
    nod *p = varfuri[varf];
    while(p){
        if(!vizitat[p->val]){
            dfs1(p->val);
        }
        p = p->next;
    }
    Stiva.push(varf);

}

void dfs2(int varf, int contorComp){

vizitatT[varf] = 1;
nod *p = varfuriT[varf];
componente[contorComp].push_back(varf);

while(p){
    if(!vizitatT[p->val]){
        dfs2(p->val, contorComp);
    }
    p = p->next;
}

}

void parcurgere(){
    for(int i = 1;i<=nrVarfuri;++i){
        if(!vizitat[i]){
            dfs1(i);
        }
    }

}

void componenteTare(){

    int contorComp = 0;
    while(!Stiva.empty()){

        int varf = Stiva.top();
        Stiva.pop(); /// nu l mai folosim
        if(!vizitatT[varf]){
            contorComp++;
            dfs2(varf, contorComp);
        }
    }

    fout<<contorComp<<endl;
    for(int i = 1;i<=contorComp;++i){
        int lungime = componente[i].size();
        for(int j = 0;j<lungime;++j){
            fout<<componente[i][j]<<" ";
        }
        fout<<endl;
    }


}


pair<long long,vector<pair<int,int> > > Kruskall(){

    sort (edges.begin(), edges.end(), comparare_functie) ;
    vector < pair< int,int > > sol;io\l]p
    for(int i=1; i <= nrVarfuri; i++)

        vizitat[i] = i;


    long long cost=0;

    for(auto it : edges)
    {
        int x = it.first;
        int y = it.second.first;
        int z = it.second.second;

        int tataX = vizitat[x];
        int tataY = vizitat[y];

        if(tataX != tataY)
        {
            cost+=z;
            for(int i = 1;i<=nrVarfuri;++i){
                if(vizitat[i] == tataX)vizitat[i] = tataY;
            }
            sol.push_back(make_pair(y,x));
        }
    }


    return make_pair(cost,sol);

}

};


int main()
{

    ComponenteTareConexe g;
    g.citireOrientat();

    pair<long long,vector<pair<int,int> > > solution = g.Kruskall();

    fout<<solution.first<<endl;
    fout<<g.getNrVarfuri()-1<<endl;

    for(auto it:solution.second)
       fout<<it.first<<' '<<it.second<<"\n";
    return 0;
}