#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX=2000005;
int dad[NMAX],rang[NMAX];
int n,m;
struct Muchie
{
  int x,y,c;
};

vector<Muchie> muchii;
vector <Muchie> muchii_arbore;

void read()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        Muchie mc;
        fin >> mc.x >> mc.y >> mc.c;
        muchii.push_back(mc);
    }
}

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

void Union(int x, int y)
{
    if(rang[x]<rang[y])
    {
        dad[x]=y;
    }else if(rang[x]>rang[y])
    {
        dad[y]=x;
    }
    else
    {
        dad[x]=y;
        rang[y]++;
    }
}
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 sum_cost=0;
    int muchii_tot=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)
        {
            muchii_arbore.push_back(muchii[i]);
            muchii_tot++;
            sum_cost+=c;
            Union(repr_x,repr_y);
        }
    }
    fout << sum_cost << "\n";

    fout << n-1 << "\n";
    for(auto muchie:muchii_arbore)
    {
        fout << muchie.x << " " << muchie.y <<"\n";
    }
    return 0;
}