/*#include <iostream>
#include <fstream>

using namespace std;

ifstream f("date.in");
const int NMAX=100005;
int dad[NMAX],rang[NMAX];
int n,m;

void read()
{
    f>>n>>m;
}

void Union(int nod1,int nod2)
{
    if(rang[nod1]<rang[nod2])
    {
        dad[nod1]=nod2;

    }
    else if(rang[nod1]>rang[nod2])
    {
        dad[nod2]=nod1;
    }
    else
    {
        dad[nod2]=nod1;
        rang[nod1]++;
    }
}

int Find(int nod)
{
    if(nod!=dad[nod]) ///PROBLEMA
    {
        int repr=Find(dad[nod]);
        dad[nod]=repr;   ///PROBLEMA
        return repr;
    }
    return nod;
}

int main()
{
    read();
    for(int i=1;i<=n;i++)
    {
        dad[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int cod,x,y;
        f>>cod>>x>>y;
        if(cod==1)
        {
            Union(x,y);
        }
        else
        {
            if(Find(x)==Find(y))
            {
                cout<<"DA\n";
            }
            else cout<<"NU\n";
        }
    }


    return 0;
}*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
const int NMAX=200005;
int dad[NMAX],rang[NMAX];
vector <int> G[NMAX];
int n,m;
struct muchie
{
    int x,y,c;
};

vector <muchie> muchii;
vector <muchie> arbore;



void read()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        muchie aux;
        f>>aux.x>>aux.y>>aux.c;
        muchii.push_back(aux);
    }
}

int Find(int nod)
{

    if(nod!=dad[nod])
    {
        int repr=Find(dad[nod]);
        dad[nod]=repr;
        return repr;
    }
    return nod;
}


void Union(int nod1,int nod2)
{
    if(rang[nod1]<rang[nod2])
    {
        dad[nod1]=nod2;
    }
    else if(rang[nod1]>rang[nod2])
    {
        dad[nod2]=nod1;
    }
    else
    {
        dad[nod1]=nod2;
        rang[nod2]++;
    }
}


int main()
{
    read();
    for(int i=1;i<=n;i++)
    {
        dad[i]=i;
    }
    sort(muchii.begin(), muchii.end(),[](muchie m1, muchie m2)
    {
        return m1.c < m2.c;
    });
    int suma=0;
    int nr_muchii=0;
    for(int i = 0; i < muchii.size(); i++){
        int x = muchii[i].x;
        int y = muchii[i].y;
        int c = muchii[i].c;
        int repr_x = Find(x);
        int repr_y = Find(y);
        if(repr_x != repr_y){
            arbore.push_back(muchii[i]);
            suma += c;
            nr_muchii++;
            Union(repr_x, repr_y);
        }
    }
    cout<<suma<<'\n';
    cout<<n-1<<'\n';
    for(auto muchiee:arbore)
    {
        cout<<muchiee.x <<" "<<muchiee.y<<'\n';
    }

    return 0;
}