//HighFLow
#include <cstdio>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
FILE *f,*g;
#define ll (long long)
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c);
#define cat(c) while(c!='\n') scanf("%c",&c);
int T[200200],Y[200200];
int i,x,y,z,s,n,m;
vector <pair<int,int> > sol;

struct cp{int x,y,z;
          cp(){}
          cp(int a,int b,int c)
          {
              x=a;
              y=b;
              z=c;
          }
            };
vector <cp> E;

void unite(int x,int y)
{
    if (Y[x]<Y[y])
        T[x]=y;
    else
        T[y]=x;

    if (Y[x]==Y[y]) Y[x]++;
}

int rad(int x)
{
    int y,z;

    for (y=x;T[y]!=y;y=T[y]) ;

    for (;T[x]!=x;)
    {
        z=T[x];
        T[x]=y;
        x=z;
    }

    return y;
}


bool cmp(cp x,cp y)
{
    return (x.z<=y.z);
}

int main()
{
	f=fopen("apm.in","r");
	g=fopen("apm.out","w");

    fscanf(f,"%d%d",&n,&m);

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        E.push_back(cp(x,y,z));
    }

    stable_sort(E.begin(),E.end(),cmp);

    for (i=1;i<=n;i++) T[i]=i,Y[i]=1;

    for (i=0;i<m;i++)
    {
        if ( rad(E[i].x)!=rad(E[i].y))
            {
                unite(rad(E[i].x),rad(E[i].y));
                s+=E[i].z;
                sol.push_back(make_pair(E[i].x,E[i].y));
            }
    }

    fprintf(g,"%d\n",s);
    fprintf(g,"%d\n",sol.size());
    for (i=0;i<sol.size();i++) fprintf(g,"%d %d\n",sol[i].first,sol[i].second);

	return 0;
}