#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int> > sol;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,cost;}v[400001];
int ct,ms,t[200001],h[200001] ;
long 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,min,max=0,u,w,h1,h2;
    fin>>n>>m;
    while(fin>>x>>y>>z)
    {
        v[k].x=x;
        v[k].y=y;
        v[k].cost=z;
        k++;
    }
    sort(v,v+k,comp);
    ms=0;
    m=0;
    while(ms<n-1)
    {
     //u=s[v[m].x];
     u=radacina(v[m].x);
     //w=s[v[m].y];
     w=radacina(v[m].y);
     if(u!=w)
     {
       ct=ct+v[m].cost;

    sol.push_back(make_pair(v[m].x,v[m].y));
    ms++;

            h1=h[v[m].x];
            h2=h[v[m].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;

}