#include<fstream>
#include<queue>
#include<vector>
#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; }

priority_queue <Muchie, vector<Muchie>, greater<Muchie> > H;
vector <Muchie> sol;
int tata[nmax], h[nmax];
int n,nrm,costmin;

void Citire()
{
    Muchie m;
    int i;
    fin>>n>>nrm;
    for(i = 0; i < nrm; i++)
    {
        fin>>m.x>>m.y>>m.cost;
        H.push(m);
    }
}

int Find(int x)
{
    int r=x;
    while(tata[r]) r=tata[r];

    int y=x,aux;
    while(y != r) { aux=tata[y]; tata[y]=r; y=aux; }
    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 Afisare()
{
    fout<<costmin<<'\n'<<n-1<<'\n';
    for(int i=0; i < n-1; i++)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
}
int main()
{
    int c1, c2;
    Muchie m;
    Citire();
    while((int)sol.size()<n-1)
    {
        m = H.top(); H.pop();
        c1=Find(m.x); c2=Find(m.y);
        if(c1!=c2)
        {
            costmin+=m.cost;
            sol.push_back(m);
            Union(c1,c2);
        }
    }
    Afisare();
    return 0;
}