#include <fstream>
#include <queue>
#define NMAX 200002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie
{
    int x,y;
    int cost;
    friend bool operator > ( const Muchie& , const Muchie&);
};
bool operator >( const Muchie& m1, const Muchie& m2)
{
    return m1.cost>m2.cost;
}
priority_queue < Muchie , vector < Muchie > , greater <Muchie > > H;
vector <Muchie> sol;
int tata[NMAX];
int h[NMAX];
int n;
int costmin;
void citire();
void afisare();
int gasire(int x);
void unire(int x, int y);
int main()
{
    int c1,c2;
    Muchie m;
    citire();
    while(sol.size()<n-1)
    {
        m=H.top();
        H.pop();
        c1=gasire(m.x);
        c2=gasire(m.y);
        if(c1!=c2)
        {
         costmin+=m.cost;
         sol.push_back(m);
         unire(c1,c2);
        }
    }
    afisare();
    return 0;
}
void citire()
{
    Muchie m;
    int nrm;
    fin >> n >> nrm;
    for (int i = 1; i <= nrm; i++)
    {
        fin >> m.x >> m.y >> m.cost;
        H.push(m);
    }
}
int gasire(int x)
{
    int r;
    r=x;
    while(tata[r])
            r=tata[r];
    while(tata[x])
    {
        int r2=tata[x];
        tata[x]=r;
        x=r2;
    }
    return r;
}
void unire(int x, int y)
{
     x=gasire(x);
     y=gasire(y);
     if(x==y)
        return;
     if(h[x]<h[y])
     {
        tata[x]=y;
     }
    if(h[x]>h[y])
            tata[y]=x;
    if(h[x]==h[y])
     {
         tata[x]=y;
         h[y]++;
     }
}
void afisare()
{

    fout << costmin << '\n';
    fout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++)
    {
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    }
}