#include <fstream>
#include <vector>
#include <queue>
#define Nmax 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

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);
}

int N, nrm, costmin, GR[Nmax];
vector<Muchie> sol;
priority_queue<Muchie, vector<Muchie>, greater<Muchie> > H;

int grupa(int i)
{
    if (GR[i] == i) return i;
    GR[i] = grupa(GR[i]);
    return GR[i];
}

void reuniune(int i,int j)
{
    GR[grupa(i)] = grupa(j);
}

void citire()
{
    Muchie m;
    fin>>N>>nrm;
    for(int i=1; i<=nrm; i++)
    {
        fin>>m.x>>m.y>>m.cost;
        H.push(m);
    }
}

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

int main()
{
    int c1, c2; Muchie m;
    citire();
    for(int i = 1;i <= N; ++i) GR[i] = i;
    while(sol.size() < N-1)
    {
        m=H.top(); H.pop();
        c1=grupa(m.x); c2=grupa(m.y);
        if(c1!=c2)
        {
            costmin += m.cost; sol.push_back(m);
            reuniune(c1, c2);
        }
    }
    afisare();
    return 0;
}