#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;};

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[200001];
long n,m;
int radacina(int x)
{
    while(t[x])
    x=t[x];
    return x;

}

int main()
{
    int i,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);
    }
    ms=0;
    ct=0;
    while(ms<n-1)
    {
     e=CP.top();
     CP.pop();
     u=radacina(e.x);
     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);
}