#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdio.h>

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,Size;

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)
{
    if(V[k] == k)
        return k;
    return root(V[k]);
}


void join(int k,int l)
{
    ///cout<<"Error starts\n";
    int kroot = root(k);
    int lroot = root(l);

    //cout<<kroot<<" "<<lroot<<endl;
    if(Size[kroot] < Size[lroot])
    {
        V[kroot] = lroot;
        Size[lroot] += Size[kroot];
    }
    else
    {
        V[lroot] = kroot;
        Size[kroot] += Size[lroot];

    }


    //cout<<"Error ends\n";
}

int main()
{
    FILE *fin = fopen("apm.in","r");
    FILE *fout = fopen("apm.out","w");
    int n,m;
//    fin>>n>>m;
    fscanf(fin,"%d %d",&n,&m);

    Size.resize(n+10);
    fill(Size.begin(),Size.end(),1);
    VECTOR_OF_EDGES E,R;
    init_set(n);

    for(int i=0;i<m;i++)
    {
        edge curr;

        //fin>>curr.from>>curr.to>>curr.val;
        fscanf(fin,"%d %d %d",&curr.from,&curr.to, &curr.val);
        E.push_back(curr);
    }


    sort(E.begin(),E.end(),compare);
    //print_edges(E);
    cout<<"Done"<<endl;
    int cost = 0;
    //print_nodes(V);
    size_t E_size = E.size();
    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()<<"\n";
    fprintf(fout,"%d\n%d",cost,R.size());
    size_t R_size = R.size();
    for(int i=0;i<R_size;i++)
        //fout<<R[i].from<<" "<<R[i].to<<"\n";
        fprintf(fout,"%d %d",R[i].from,R[i].to);
    //print_nodes(V);
}