#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[100];
int n,m,s[100],ct,ms,h1,h2;
int t[100001],h[100001];
int radacina(int x)
{
    while(t[x]!=0)
        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;
    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);
    for(i=1;i<=n;i++)
    s[i]=i;
    ms=0;
    m=0;
    while(ms<n-1)
    {
     u=radacina(v[m].x);
     w=radacina(v[m].y);
     if(u!=w)
     {
       ct=ct+v[m].cost;
    //fout<<v[m].x<<' '<<v[m].y<<endl;
    sol.push_back(make_pair(v[m].x,v[m].y));
    ms++;
    //for(j=1;j<=n;j++)if(s[j]==w)s[j]=u;
    h1=h[v[m].x];
    h2=h[v[m].y];
    if(h1<h2)
    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;
}