#include <bits/stdc++.h>
#define nm 200005
#define nmm nm*(nm-1)/2
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muc{int x,y,c;} g[nm];
int a[nm], c[nm];
int n,m;
bool cmp (muc a, muc b) {return a.c>b.c;};
int main()
{
    int i,j,mni,mxa,nr=0,cost=0;
    fin>>n>>m;
    for(i=1;i<=m;++i)
        fin>>g[i].x>>g[i].y>>g[i].c;
    for(i=1;i<=n;++i)
        c[i]=i;
    sort(g,g+n,cmp);
    for(i=1; nr<n-1; ++i)
      if(c[g[i].x]!=c[g[i].y])
    {
        a[++nr]=i; cost+=g[i].c;
        mxa=max(c[g[i].x],c[g[i].y]);
        mni=min(c[g[i].x],c[g[i].y]);
        for(j=1;j<n;++j)
            if(c[j]==mxa) c[j]=mni;
    }
    fout<<cost;
    fout<<"\n"<<n-1<<"\n";
     for(i=1;i<n;++i)
        fout<<g[a[i]].x<<" "<<g[a[i]].y<<"\n";
}