#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200001,M=400001,P=10000000;
int d[N],x[M],y[M],c[M],n,m,e,p[M],l[N],i,j,o,t;
char r[P];
int A()
{
  	int s=0,f=1;
  	if(r[o+1]=='-')
        f=-1,o++;
  	for(o++;r[o]>='0'&&r[o]<='9';o++)
  		s=s*10+r[o]-'0';
  	return s*f;
}
void S(int x,char c)
{
    int i,d;
    if(x<0)
        x=-x,r[t++]='-';
    d=x>999999999?10:x>99999999?9:x>9999999?8:x>999999?7:x>99999?6:x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,i--)
        r[t+i]=x%10+48;
    r[t+d]=c,t+=d+1;
}
int E(int x)
{
    if(d[x]==x)
        return x;
    d[x]=E(d[x]);
    return d[x];
}
void R(int x,int y)
{
    d[E(x)]=E(y);
}
bool F(int a,int b)
{
    return c[a]<c[b];
}
int main()
{
    freopen("apm.in","r",stdin),freopen("apm.out","w",stdout),fread(r,1,P,stdin),n=A(),m=A();
    for(i=0;i<m;i++)
        x[i]=A(),y[i]=A(),c[i]=A(),d[i]=p[i]=i;
    sort(p,p+m,F);
    for(i=0;i<m;i++)
        if(E(x[p[i]])!=E(y[p[i]]))
            e+=c[p[i]],R(x[p[i]],y[p[i]]),l[j++]=p[i];
    S(e,'\n'),S(n-1,'\n');
    for(i=0;i<n-1;i++)
        S(x[l[i]],' '),S(y[l[i]],'\n');
    fwrite(r,1,t,stdout);
}