#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie{int x,y,c;};
muchie e[1000];
int z[100],n,m,i,j,x,y,ct,nr,u,v;
vector <pair < int ,int > > sol;
ifstream fin("apm.in");
ofstream fout("apm.out");
int comparare(muchie a, muchie b)
{
    return a.c<b.c;
}
int main()
{
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>e[i].x>>e[i].y>>e[i].c;
      /*
   for (i=1; i<m; i++)
        for(j=i+1; j<=m; j++)
            if(e[i].c>e[j].c)
            {
                muchie aux;
                aux=e[i];
                e[i]=e[j];
                e[j]=aux;
            }
            */
    sort(e+1, e+m+1, comparare);
    for(i=1; i<=n; i++) z[i]=i;
    ct=0;
    nr=0;
    i=1;
    while(nr<n-1)
    {
        u=z[e[i].x];
        v=z[e[i].y];
        if(u!=v)
        {
            sol.push_back(make_pair(e[i].x, e[i].y));
            for(j=1; j<=n; j++)
                if(z[j]==v) z[j]=u;
            ct=ct+e[i].c;
            nr=nr+1;
        }
        i++;
    }
    fout<<ct<<endl<<n-1<<endl;
    for(i=0; i<sol.size(); i++)
        fout<<sol[i].first<<' '<<sol[i].second<<endl;
    return 0;
}