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