#include <iostream>
#include <fstream>
#include<algorithm>
#include <vector>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int tati[200001],inaltimi[200001];
pair<int,pair<int,int>>muchii[200001];
vector<pair<int,int>>rasp;
int n,m,c,x,y;
int cost;
int gasire_tata(int x)
{
    while(tati[x]!=x)
    {
        x = tati[x];
    }
    return x;
}
void aplatizare(int x,int tata)
{
    while(tati[x]!=x)
    {
        x = tati[x];
        tati[x] = tata;
    }
}
void unire(int x1,int x2)
{
    int tata1 = gasire_tata(x1);
    int tata2 = gasire_tata(x2);
    aplatizare(x1,tata1);
    aplatizare(x2,tata2);
    if(inaltimi[tata1]>inaltimi[tata2])
    {
        inaltimi[tata2] = inaltimi[tata1];
        tati[tata2] = tata1;
    }
    else if(inaltimi[tata1]<inaltimi[tata2])
    {
        inaltimi[tata1]=inaltimi[tata2];
        tati[tata1] = tata2;
    }
    else
    {
        tati[tata1] = tata2;
        inaltimi[tata2]++;
    }
}
void init()
{
    for(int i= 1; i<=n; i++)
    {
        tati[i] = i;
        inaltimi[i] = 1;
    }
    sort(muchii+1,muchii+1+m);
}
void citire()
{
    f >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f >> x >> y >> c;
        muchii[i].first = c;
        muchii[i].second.first = x;
        muchii[i].second.second = y;
    }

}
void rez()
{
    for(int i =1 ; i<=m; i++)
    {
        int x = muchii[i].second.first,y = muchii[i].second.second,c = muchii[i].first;
        if(gasire_tata(x) != gasire_tata(y))
        {
            unire(x,y);
            rasp.push_back({x,y});
            cost+=c;
        }
    }
}
void afisare()
{
    g<< cost<<endl;
    g << rasp.size()<< endl;
    for(int i = 0;i<rasp.size();i++)
    {
        g << rasp[i].first<< " " << rasp[i].second<<'\n';
    }
}
int main()
{
    citire();
    init();
    rez();
    afisare();
}