/***************    Algoritm Kruskal (varianta n*n + m* log n)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct Muchie{
    int u,v,w;
    Muchie(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
};
bool comparator(Muchie &m1,Muchie &m2)
{
    return m1.w<m2.w;
}
int n,m;
vector<Muchie> muchii;
vector<int> Reprez;
vector<pair<int,int>> Rezultat;
void Init() // Initial, fiecare muchie este o componenta deoarece nu exista muchii. Adaugam muchiile intr-un vector si il sortam dupa greutate
{
    for(int i=1;i<=n;i++)
        Reprez[i] = i;
    for(int i=0;i<m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        muchii.push_back(Muchie(x,y,w));
    }
    sort(muchii.begin(),muchii.end(),comparator);
}
void Reuneste(int u,int v) // Reunim componentele, deci toti reprezentantii nodurilor din aceste componente o sa ia aceeasi valoare
{
    int r1 = Reprez[u];
    int r2 = Reprez[v];
    for(int i=1;i<=n;i++)
        if(Reprez[i] == r2)
            Reprez[i] = r1;
}
int main()
{
    cin>>n>>m;
    Reprez.resize(n+1);
    Init();
    int NrMuchii=0,GreutateTotala=0;
    for(int i=0;i<m;i++)
    {
        if(Reprez[muchii[i].u]!=Reprez[muchii[i].v]) // Daca nu fac parte din aceeasi componenta, le reunim
        {
            GreutateTotala+=muchii[i].w;
            NrMuchii++;
            Rezultat.push_back(make_pair(muchii[i].u,muchii[i].v));
            Reuneste(muchii[i].u,muchii[i].v);
        }
        if(NrMuchii == n-1)
            break;
    }
    cout<<GreutateTotala<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        cout<<Rezultat[i].first<<' '<<Rezultat[i].second<<'\n';
    return 0;
}
***************/
/***************    Algoritmul lui Kruskal (varianta m*logn)*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
struct Muchie{
    int u,v,w;
    Muchie(int u,int v,int w){
        this->u = u;
        this->v = v;
        this->w = w;
    }
};
vector<int> ranc,parinte;
vector<pair<int,int>> rez;
vector<Muchie> muchii;
void Init(){
    for(int i=1;i<=n;i++)
    {
        ranc[i] = 1;
        parinte[i] = i;
    }
}
int gaseste_radacina(int u){
    return (parinte[u] == u?u:parinte[u] = gaseste_radacina(parinte[u]));
}
bool uneste(int u, int v)
{
    int r1 = gaseste_radacina(u);
    int r2 = gaseste_radacina(v);
    if(r1!=r2){
        rez.push_back(make_pair(u,v));
        if(ranc[r1]<ranc[r2]) parinte[r1] = r2;
        else if(ranc[r1] > ranc[r2]) parinte[r2] =r1;
        else parinte[r2] = r1,ranc[r1]++;
        return 1;
    }
    return 0;
}
bool comparator(Muchie &m1,Muchie &m2){
    return m1.w<m2.w;
}
int main()
{
    int GreutateTotala=0;
    cin>>n>>m;
    ranc.resize(n+1);
    parinte.resize(n+1);
    Init();
    for(int i=0;i<m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        muchii.push_back(Muchie(x,y,w));
    }
    sort(muchii.begin(),muchii.end(),comparator);
    for(int i=0;i<m;i++)
        if(uneste(muchii[i].u,muchii[i].v))
            GreutateTotala+=muchii[i].w;
    cout<<GreutateTotala<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        cout<<rez[i].first<<' '<<rez[i].second<<'\n';
    return 0;
}