#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#define nmax 200001
#define pb push_back
#define mkp make_pair
using namespace std;

FILE *f1=fopen("apm.in","r"),*f2=fopen("apm.out","w");
vector<pair<int,pair<int,int> > > v;
vector <pair<int,int> > sol;
int n,m,nr,cost;
int RG[nmax],TT[nmax];
int h,g;
int search1(int x)
{
     int r=x,aux;
        while(r!=TT[r])r=TT[r];
        while(x!=TT[x]){aux=TT[x];TT[x]=r;x=aux;}
    return r;
}
void unite (int x, int y)
{
  if(RG[x]>RG[y])TT[g]=h;
  else TT[h]=g;
  if (RG[x] == RG[y]) {RG[y]++;}
}

int main()
{
    fscanf(f1,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fscanf(f1,"%d%d%d",&x,&y,&c);
        v.pb(mkp(c,mkp(x,y)));
    }
    sort(v.begin(),v.end());

     for(int i=1;i<=n;i++)
    {
        TT[i]=i;
        RG[i]=1;
    }

    for(int i=0;i<m;i++)
    {
        int x=v[i].second.first,
            y=v[i].second.second;
            h=search1(x);
            g=search1(y);
        if(h!=g)
        {
            cost+=v[i].first;
            sol.pb(mkp(x,y));
            unite(x,y);
        }
    }
    fprintf(f2,"%d\n%d\n",cost,n-1);
    for(int i=0;i<n-1;i++)
    fprintf(f2,"%d %d\n",sol[i].first,sol[i].second);
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.