#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define N 200005
#define oo 2000000000
using namespace std;
int n,m;
struct str
{
    int x,y,c;
};
int sol[2][N];
int v[N];
int compcon[N];
int suma,top;
vector <str> a;

bool Comp(str g,str h)
{
    return g.c<h.c;
}

void Read()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    int xx,yy,cost,i;
    str w;
    for( i=1; i<=m; i++)
    {
        fin>>w.x>>w.y>>w.c;
        a.push_back(w);
    }
    sort(a.begin(),a.begin()+a.size(),Comp);

}
bool Verifica(int i)
{
    if(v[a[i].x]==v[a[i].y] && v[a[i].x]==1)
        return 0;
    return 1;
}
void Unite(int good, int bad)
{
    for(int i=1; i<=n; i++)
        if(compcon[i]==bad) compcon[i]=good;
}
void Adauga(int i)
{
    top++;
    sol[0][top]=a[i].x;
    sol[1][top]=a[i].y;
    suma+=a[i].c;
}

void Ini()
{
    for(int i=1; i<=n; i++)
        compcon[i]=i;
}
void Salv()
{
    Ini();
   int nrm=n-1,compx,compy;
   int i=0;
   int nr=0;
   while(nrm && i<m)
   {
       compx=compcon[a[i].x];
       compy=compcon[a[i].y];
        if(compx!=compy)
        {
            Unite(compx,compy);
            Adauga(i);
            nrm--;
        }
       i++;
   }
}
int main()
{
    ofstream fout("apm.out");
   Read();
   Salv();
   fout<<suma<<"\n"<<top<<"\n";
   for(int i=1; i<=top; i++)
    fout<<sol[0][i]<<" "<<sol[1][i]<<"\n";

    return 0;
}