#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int,int> > sol;
//ifstream fin("apm.in");
//ofstream fout("apm.out");
FILE*fin=fopen("apm.in","r");
FILE*fout=fopen("apm.out","w");
struct muchie{int x,y,cost;}v[100];

struct compar{
  bool operator()(muchie a, muchie b)
  {return b.cost<a.cost;}};

priority_queue<muchie, vector <muchie>, compar>CP;

int ct,ms,t[200001],h[200000];
long n,m;
int radacina(int x)
{
    while(t[x])
    x=t[x];
    return x;

}
int comp(const muchie&a,const muchie&b)
{
     return a.cost<b.cost;
}

int main()
{
    int x,y,z,k=0,i,j,u,w,h1,h2;
    //fin>>n>>m;
    fscanf(fin,"%d %d",&n,&m);
    muchie e;
    for(i=1;i<=m;i++)
    {
      //fin>>e.x>>e.y>>e.cost;
      fscanf(fin,"%d %d %d",&e.x,&e.y,&e.cost);
    CP.push(e);
    }
    /*while(fin>>x>>y>>z)
    {
        v[k].x=x;
        v[k].y=y;
        v[k].cost=z;
        k++;
    }*/

    ms=0;
    ct=0;
    while(ms<n-1)
    {
     e=CP.top();
     CP.pop();
     //u=s[v[m].x];
     u=radacina(e.x);
     //w=s[v[m].y];
     w=radacina(e.y);
     if(u!=w)
     {
       ct=ct+e.cost;

    sol.push_back(make_pair(e.x,e.y));
    ms++;

            h1=h[e.x];
            h2=h[e.y];
            if(h1<h2)
            t[u]=w;
            else if(h1>h2)
            t[w]=u;
            else{t[u]=w;
            h[w]++;}


     }

    }

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