#include <cstdio>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

class DisjointSets{
    struct Node{
        int key;
        int rang;
    };

    vector<Node> T;

    public :

        DisjointSets(){}
        DisjointSets(size_t sz){
            T.resize(sz);
            for(int i = 0; i < sz; ++i){
                T[i].key = i;
                T[i].rang = 1;
            }
        }
        int Find(int);
        void Union(int,int);
};

struct edge{

    int i,j,w;

    edge(){}

    inline friend bool operator < (const edge& e1, const edge& e2){
        if(e1.w != e2.w)
            return e1.w < e2.w;
        else
            return e1.j < e2.j;
    }

    /*friend istream &operator >> (istream &is, edge& e)
    {
        is >> e.i;
        is >> e.j;
        is >> e.w;
        return is;
    }

    friend ostream &operator << (ostream &os, const edge& e)
    {
        os << e.j << " " << e.i;
        os << endl;
        return os;
    }*/
};

int cost = 0;

inline void Kruskal(vector <edge>,int);

vector <edge> T;

vector<edge>::iterator it;

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n , m;
    edge e;
    vector <edge> E;
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d",&e.i,&e.j,&e.w);
        E.push_back(e);
    }
    fclose(stdin);
    Kruskal(E,n);
    printf("%i\n%i\n",cost,T.size());
    for(it = T.begin(); it != T.end(); ++it)
         printf("%d %d\n",(*it).j,(*it).i);
    fclose(stdout);
    return EXIT_SUCCESS;
}

void Kruskal(vector <edge> E, int n)
{
    sort(E.begin(),E.end());
    DisjointSets S(n);
    for(it = E.begin(); it != E.end(); ++it){
        int x = (*it).i-1;
        int y = (*it).j-1;
        if(S.Find(x) != S.Find(y)){
            S.Union(S.Find(x),S.Find(y));
            cost += (*it).w;
            T.push_back(*it);
        }
    }
}

inline int DisjointSets::Find(int x)
{
    int R, y;

    //merg in sus pe arbore pana gasesc un nod care pointeaza catre el insusi
    for (R = x; T[R].key != R; R = T[R].key);

    //aplic compresia drumurilor
    for (; T[x].key != x;)
    {
        y = T[x].key;
        T[x].key = R;
        x = y;
    }
    return R;
}

inline void DisjointSets::Union(int x, int y)
{
	//unesc multimea cu rang mai mic de cea cu rang mai mare
	if (T[x].rang > T[y].rang)
		T[y].key = x;
    else
        T[x].key = y;

	//in caz ca rangurile erau egale atunci cresc rangul noii multimi cu 1
	if (T[x].rang  == T[y].rang)
        T[y].rang++;
}