#include <fstream>
#include <queue>
#define NMAX 200004
using namespace std;

ifstream cin("apm.in");
ofstream cout("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;
    cin >> n >> nrm;
    for (int i = 1; i <= nrm; i++)
    {
        cin >> 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()
{
    cout << costmin << '\n';
    cout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++)
    {
        cout << sol[i].x << ' ' << sol[i].y << '\n';
    }
}