#include <iostream>
#include <iterator>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>

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;

int main()
{
    fstream in("apm.in",ios::in);
    fstream out("apm.out",ios::out);
    int n , m;
    vector <edge> E;
    vector<edge>::iterator it;
    in >> n >> m;
    for(int i = 0; i < m; ++i){
        edge e;
        in >> e;
        E.push_back(e);
    }
    Kruskal(E,n);
    out << cost << endl;
    out << T.size() << endl;
    for(it = T.begin(); it != T.end(); ++it)
        out << *it;
    return EXIT_SUCCESS;
}

void Kruskal(vector <edge> E, int n)
{
    sort(E.begin(),E.end());
    vector <edge>::iterator it;
    DisjointSets S(n);
    for(it = E.begin(); it != E.end(); ++it){
        if(S.Find((*it).i-1) != S.Find((*it).j-1)){
            S.Union(S.Find((*it).j-1),S.Find((*it).j-1));
            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++;
}