#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 998244353ll
#define nmax 400001
using namespace std;
typedef long long ll;
ifstream in("apm.in");
ofstream out("apm.out");
//FILE *fin=fopen("ghicit.in","r");
//FILE *fout=fopen("ghicit.out","w");
int n,m,i,j,k,l,f[nmax],s[nmax],x,y,z,t;
struct g{int a,b,c;}a[nmax];
int main()
{
in>>n>>m;
forq(i,0,m)in>>a[i].a>>a[i].b>>a[i].c;
forq(i,1,n+1)f[i]=i,s[i]=1;
sort(a,a+m,[](g a,g b){return a.c<b.c;});
forq(i,0,m)
{
    x=a[i].a,z=f[x];
    while(z!=f[z])z=f[z];
    while(f[x]!=z)y=f[x],f[x]=z,x=y;
    x=a[i].b,z=f[x];
    while(z!=f[z])z=f[z];
    while(f[x]!=z)y=f[x],f[x]=z,x=y;
    printf("%d %d | %d %d\n",a[i].a,f[a[i].a],a[i].b,f[a[i].b]);
    if(f[a[i].a]!=f[a[i].b])
        if(s[f[a[i].a]]>s[f[a[i].b]])
            s[f[a[i].a]]=s[f[a[i].b]],s[f[a[i].b]]=0,f[f[a[i].b]]=f[a[i].a],t+=a[i].c;
            else s[f[a[i].b]]=s[f[a[i].a]],s[f[a[i].a]]=0,f[f[a[i].a]]=f[a[i].b],t+=a[i].c;
        else a[i].a|=-1;
}
out<<t<<'\n'<<n-1<<'\n';
forq(i,0,m)
    if(a[i].a>0)
        out<<a[i].a<<' '<<a[i].b<<'\n';
}