#include <fstream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
FILE *fin=fopen("apm.in","r");
FILE *fout=fopen("apm.out","w");
struct muchie{int x,y,c;};
vector <pair <int,int> > sol;
int n,m,i,t[200001],CT,nr,u,v,h1,h2,h[200001];
struct compar
{
    bool operator()(muchie a, muchie b)
    {
        return b.c<a.c;
    }
};
priority_queue<muchie,vector<muchie>, compar> cp;
int radacina(int x)
{
    while (t[x]!=0) x=t[x];
    return x;
}
int main()
{
    fscanf(fin,"%d %d", &n, &m);
    muchie e;
    for(i=1; i<=m; i++)
    {
        fscanf(fin, "%d %d %d", &e.x, &e.y, &e.c);
        cp.push(e);
    }
    CT=0;
    nr=0;
    while(nr<n-1)
    {
        e=cp.top();
        cp.pop();
        u=radacina(e.x);
        v=radacina(e.y);
        if (u!=v)
        {
            sol.push_back(make_pair(e.x,e.y));
            CT=CT+e.c;
            nr++;
            h1=h[u];
            h2=h[v];
            if(h1<h2)
                t[u]=v;
            else if(h2<h1)
                t[v]=u;
            else {t[v]=u; h[u]++;}
        }
    }
    fprintf(fout,"%d\n",CT);
    fprintf(fout,"%d\n",nr);
    for(i=0; i<sol.size(); i++)
    {
        fprintf(fout,"%d %d\n", sol[i].first, sol[i].second);
    }
    return 0;
}