#include<cstdio>
#include<algorithm>
using namespace std;
const int nmax = 200005;
const int mmax = 400005;
int n,m,i,f[nmax],fx,fy,sol,a[nmax],b[mmax],cnt;
struct edge {int x,y,c;} e[mmax];
struct cmp
{
    bool operator () (edge a,edge b) const
    {
        return a.c<b.c;
    }
};
int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void unite(int x,int y)
{
    f[x]=y;
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
	sort(e+1,e+m+1,cmp());
	for(i=1;i<=n;i++) f[i]=i;
	for(i=1;i<=m;i++)
	{
	    fx=find(e[i].x);
	    fy=find(e[i].y);
	    if(fx==fy) continue;
	    unite(fx,fy);
	    sol+=e[i].c;
	    a[++cnt]=e[i].x;
	    b[cnt]=e[i].y;
	}
	printf("%d\n%d\n",sol,cnt);
	for(i=1;i<=cnt;i++) printf("%d %d\n",a[i],b[i]);
	return 0;
}