#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int t[N],h[N];
struct Pair{
int x,y,c;
} v[N],sol[N];
bool cmp(Pair a, Pair b){
return a.c<b.c;
}
int Find(int x){
if(x==t[x]) return x;
t[x]=Find(t[x]);
return t[x];
}
void Union(int x, int y){
if(h[x]==h[y]){
t[y]=x;
h[x]++;
}
else{
if(h[x]>h[y]) t[y]=x;
else t[x]=y;
}
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int n,m,i,j,a,b,c,s=0,cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
v[i]={a,b,c};
}
sort(v+1,v+m+1,cmp);
for(int i=1;i<=n;i++) t[i]=i;
//for(int i=1;i<=m;i++) printf("%d %d %d\n",v[i].x,v[i].y,v[i].c);
for(int i=1;i<=m;i++){
a=Find(v[i].x);
b=Find(v[i].y);
if(a!=b){
Union(a,b);
s+=v[i].c;
sol[++cnt]=v[i];
}
if(cnt==n-1) break;
}
printf("%d\n%d\n",s,n-1);
for(int i=1;i<n;i++) printf("%d %d %d\n",sol[i].y,sol[i].x,sol[i].c);
return 0;
}