#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#define Nmax 200002
using namespace std;

struct muchie
{
    int x, y, cost;
    friend bool operator > (const muchie &, const muchie &);
};

bool operator > (const muchie & m1, const muchie & m2)
{
    return m1.cost>m2.cost;
}

vector < muchie > sol;
priority_queue < muchie, vector < muchie >, greater < muchie > > q;
int h[Nmax], tata[Nmax];
int n, costmin;

void read()
{
    int nrm;
    ifstream f("apm.in");
    f >> n >> nrm;
    muchie m;
    for(int i=0; i<nrm; ++i)
    {
        f >> m.x >> m.y >> m.cost;
        q.push(m);
    }
    f.close();
}

int Find(int x)
{
    int r=x;
    while (tata[r])
        r=tata[r];
    int y=x, t;
    while(y!=r)
    {
        t=tata[y];
        tata[y]=r;
        y=t;
    }
    return r;
}

void Union(int c1, int c2)
{
    if(h[c1]>h[c2]) tata[c2]=c1;
    else
    {
        tata[c1]=c2;
        if(h[c1]==h[c2]) h[c2]++;
    }
}

void kruskal()
{
    int c1, c2;
    muchie m;
    while(sol.size()<n-1)
    {
        m=q.top(); q.pop();
        c1=Find(m.x); c2=Find(m.y);
        if(c1!=c2)
        {
            costmin+=m.cost; sol.push_back(m);
            Union(c1, c2);
        }
    }
}

void out()
{
    ofstream g("apm.out");
    g << costmin << '\n';
    g << n-1 << '\n';
    for(int i=0; i<n-1; ++i)
        g << sol[i].x << ' ' << sol[i].y << '\n';
    g.close();
}

int main()
{
    read();
    kruskal();
    out();
    return 0;
}