#include <fstream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
//ifstream f("apm.in");
//ofstream g("apm.out");
struct muchie{
int x,y,c;
};
vector<pair<int,int> >sol;
struct compar{
 bool operator()(muchie a,muchie b)
{
    return b.c<a.c;
}
};
priority_queue<muchie,vector<muchie>, compar>H;
int t[200001],hh[200001],n,m,ct;
int tata(int x)
{
    while(t[x]!=0)
        x=t[x];
    return x;
}
int main()
{
    int i,h1,h2,u,v,nr;
    muchie e;
    //f>>n>>m;
    fscanf(f,"%d %d",&n,&m);

    for(i=1;i<=m;i++)
    {
        //f>>e.x>>e.y>>e.c;
         fscanf(f,"%d %d %d",&e.x,&e.y,&e.c);
        H.push(e);
    }
    ct=0; nr=0;
    while(nr<n-1)
    {
        e=H.top();
        H.pop();
        u=tata(e.x);
        v=tata(e.y);
        if(u!=v)
        {
            nr++;
            sol.push_back(make_pair(e.x,e.y));
            h1=hh[u];
            h2=hh[v];
            ct=ct+e.c;
            if(h1<h2)
               t[u]=v;
            else if(h2<h1)
                    t[v]=u;
                   else
                   {
                   t[v]=u;
                   hh[u]++;
                   }


        }
    }
    //g<<ct<<endl;
    fprintf(g,"%d\n",ct);
    //g<<n-1<<endl;
    fprintf(g,"%d\n",n-1);
    for(i=0;i<sol.size();i++)
        //g<<sol[i].first<<' '<<sol[i].second<<endl;
        fprintf(g,"%d %d\n",sol[i].first,sol[i].second);
    return 0;
}