#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define piii pair<int ,pair<int,int> >
#define mp make_pair
#define dist first
#define nod1 second.first
#define nod2 second.second
using namespace std;
vector <pair<int,int> > rez;
FILE*in=fopen("apm.in","r");
FILE*out=fopen("apm.out","w");
int tata[200001];
int getRadacina(int n1)
{
    if(tata[n1])
    {
        tata[n1]=getRadacina(tata[n1]);
        return getRadacina(tata[n1]);
    }
    else
        return n1;
};
priority_queue<  piii ,vector< piii >,greater<piii> > q;
int main()
{
    int noduri,muchii;
    fscanf(in,"%d%d",&noduri,&muchii);
    int sum=0;
    for(int i=1;i<=muchii;++i)
    {
        int data1,data2,data3;
        fscanf(in,"%d%d%d",&data1,&data2,&data3);
        q.push(mp(data3,mp(data1,data2)));
    }
    while(!q.empty())
    {
        piii curent=q.top();
        q.pop();
        int w=getRadacina(curent.nod1);
        int q=getRadacina(curent.nod2);
        if(w!=q)
        {
            tata[w]=q;
            sum+=curent.dist;
            rez.push_back(mp(curent.nod1,curent.nod2));
        }
    }
    fprintf(out,"%d\n",sum);
    fprintf(out,"%d\n",(int)rez.size());
    for(int i=0;i<(int)rez.size();++i)
        fprintf(out,"%d %d\n",rez[i].first,rez[i].second);

fclose(in);
fclose(out);
return 0;
}