#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

list < pair<int,int> > * citire_date_intrare(int &n, int &m)
{
    f>>n>>m;
    list < pair <int,int> > *l;
    l=new list<pair <int,int> > [n+1];
    for(int i=1;i<=m;++i)
    {
        pair <int,int> x;
        pair <int,int> y;
        int c;
        f>>y.first>>x.first>>c;
        y.second=c;
        x.second=c;
        l[x.first].push_back(y);
        l[y.first].push_back(x);
    }
    return l;

}

void lista_cu_pair()
{
        int n,m;
    list < pair < int,int > > *lista;
    lista=citire_date_intrare(n,m);
    for(int i=1;i<=n;++i)
    {
        for(list < pair < int,int > > ::iterator it=lista[i].begin();it!=lista[i].end();++it)
        g<<it->first<<" "<<it->second<<"\n";
        g<<"\n\n\n";
    }
}

struct muchie
{
    unsigned int x,y,cost;
};

struct muchie * read_input_data(int &n,int &m)
{
    struct muchie * local_vector;
    f>>n>>m;
    local_vector=new muchie [m];
    for(int i=0;i<m;++i)
    {
        f>>local_vector[i].x>>local_vector[i].y>>local_vector[i].cost;
    }
    return local_vector;
}

int comparison_criterion(muchie a, muchie b)
{
    return a.cost<b.cost;
}

int find_parent(int p[],int x)
{
    if(p[x]==x) return x;
    else
    return find_parent(p,p[x]);
}

bool get_apm_from_graph(int n,int m, muchie *list_of_edges)
{
    int paduri[n+1];
    for(int i=0;i<=n;++i) paduri[i]=i;

    queue < pair <int,int> > q;
    pair <int,int> a;
    int nr_edges=0;
    int sum_lung=0;

    for(int j=0;j<m;++j)
    {
        int nodx=find_parent(paduri,list_of_edges[j].x);
        int nody=find_parent(paduri,list_of_edges[j].y);
        if(nodx!=nody)
        {
            sum_lung+=list_of_edges[j].cost;
            ++nr_edges;
            a.first=list_of_edges[j].x;
            a.second=list_of_edges[j].y;
            q.push(a);
            if(nodx>nody)
            paduri[nody]=nodx;
            else
            paduri[nodx]=nody;
        }
    }
    g<<sum_lung<<"\n"<<nr_edges<<"\n";
    while(!q.empty())
    {
        a=q.front();q.pop();
        g<<a.first<<" "<<a.second<<"\n";
    }
    return false;
}
int main()
{
    int n,m;
    muchie *list_of_edges;
    list_of_edges=read_input_data(n,m);

    sort(list_of_edges,list_of_edges+m,comparison_criterion);
    get_apm_from_graph(n,m,list_of_edges);

    return 0;
}