#include<cstdio>
#include<algorithm>
#define Nmax 500001
#define x first
#define y second
using namespace std;
int n,m,i,cm,nr;
int b[Nmax],d[Nmax];
typedef pair< int , pair< int ,int > > punct;
punct a[500001];
void cit()
{freopen("apm.in","rt",stdin); freopen("apm.out","wt",stdout);
 scanf("%d%d",&n,&m);
 for(register int i=1;i<=m;++i) scanf("%d%d%d",&a[i].y.x,&a[i].y.y,&a[i].x);
 for(register int i=1;i<=n;i++) d[i]=i;
}
int det(int x)
{int r=x,y;
 while(d[r]!=r) r=d[r];
 while(x!=d[x]) {y=d[x]; d[x]=r; x=y; }
 return r;
}
void calc()
{int m1,m2;
 for(register int i=1;i<=m && nr<n-1; i++)
	{m1=det(a[i].y.x);
	 m2=det(a[i].y.y);
	 if(m1!=m2)
		{cm+=a[i].x;
		 b[++nr]=i;
		 d[m1]=m2;
		}
	}
}
void afis()
{printf("%d\n%d\n",cm,nr);
 for(register int i=1;i<=nr;++i) printf("%d %d\n",a[b[i]].y.y,a[b[i]].y.x);
}
int main()
{cit();
 sort(a+1,a+m+1);
 calc();
 afis();
 return 0;
}