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

using namespace std;

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

typedef struct edge
{
    int from,to,val;
};

typedef vector<int> VECTOR_OF_INTS;
typedef vector<edge> VECTOR_OF_EDGES;

VECTOR_OF_INTS V;

inline bool compare(const edge &a,const edge &b)
{
    return a.val < b.val;
}

void init_set(int n)
{
    V.push_back(0);
    for(int i=1;i<=n;i++)
        V.push_back(i);
}

void print_edges(VECTOR_OF_EDGES &E)
{
    for(int i=0;i<E.size();i++)
        cout<<E[i].from<<" "<<E[i].to<<" "<<E[i].val<<endl;

}

void print_nodes(VECTOR_OF_INTS &V)
{

    for(int i=0;i<V.size();i++)
        cout<<V[i]<<" ";
    cout<<endl;
}

int root(int k)
{
    while(V[k] != k)
    {
        k = root(V[k]);
    }
}


void join(int k,int l)
{
    V[root(max(k,l))] = min(k,l);
}

int main()
{
    int n,m;
    fin>>n>>m;
    VECTOR_OF_EDGES E,R;
    init_set(n);

    for(int i=0;i<m;i++)
    {
        edge curr;
        fin>>curr.from>>curr.to>>curr.val;

        E.push_back(curr);
    }


    sort(E.begin(),E.end(),compare);
    //print_edges(E);

    int cost = 0;
    //print_nodes(V);

    for(int i=0;i<E.size();i++)
    {

        edge curr = E[i];

        if(root(curr.from) == root(curr.to))
            continue;
        //cout<<curr.from<<" "<<curr.to<<endl;
        R.push_back(curr);
        join(curr.from,curr.to);
        cost += curr.val;

    }
    fout<<cost<<endl<<R.size()<<endl;
    for(int i=0;i<R.size();i++)
        fout<<R[i].from<<" "<<R[i].to<<endl;

    //print_nodes(V);
}