#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
#define Nmax 10000
#define MAX 1001
using namespace std;
vector <pair<int,int> >G[Nmax];
vector <pair<int,int> >::iterator it;
deque <int> D;
int n;
typedef struct muchie{int lef,rig;};
muchie U[Nmax];
bool viz[Nmax];
void reading(int &n)
{
    int x,y,c,m,k;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(k=1;k<=m;++k)
    {
        scanf("%d %d %d",&x,&y,&c);
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }
}
void apm()
{
    int i,j,k=0,minim,st,dr,S=0,x;
   // for(i=1;i<=n;++i) viz[i]=0;
    viz[1]=1;D.push_back(1);
    for(i=2;i<=n;++i)
    {
        minim=MAX;
       for(j=0;j<=k;++j)
       {
               x=D[j];
         for(it=G[x].begin();it!=G[x].end();++it)
            if (it->second<minim && !viz[it->first])
            {
                minim=it->second;
                st=x;dr=it->first;
            }
       }
       S=S+minim;viz[dr]=1;
       D.push_back(dr);++k;
       U[k].lef=st;
       U[k].rig=dr;
    }
    printf("%d\n",S);
    printf("%d\n",n-1);
    for(i=1;i<=n-1;++i)
    printf("%d %d\n",U[i].lef,U[i].rig);
}
int main()
{
    reading(n);
    apm();
    return 0;
}