#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int,int> > sol;
ifstream fin("apm.in");
ofstream fout("apm.out");
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[100001],h[100000];
long long s[1000000],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,min,max=0,u,w,h1,h2;
    fin>>n>>m;
    muchie e;
    for(i=1;i<=m;i++)
    {
      fin>>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;
    m=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]++;}

     }
     m++;
    }

    fout<<ct<<endl;
    fout<<n-1<<endl;
    for(i=0;i<sol.size();i++)
        fout<<sol[i].first<<' '<<sol[i].second<<endl;

}