#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
#define Max 200001
 
int rad[Max],n,m;
bool viz[Max];
struct edge{ int x,y,c; }a[Max];

bool sort_type(edge a,edge b){return a.c < b.c;}
 
int tata(int x)
{
    if(x!=rad[x])
		rad[x]=tata(rad[x]);
    return rad[x];
}
 
void apm()
{
    int s=0,k=1;
    sort(a+1,a+m+1,sort_type);
	
    for(int i=1;i<=n;i++) 
		rad[i]=i;
	
    for(int i=1;i<n;i++)
    {
        while(tata(a[k].x)==tata(a[k].y))
			k++;
		
        rad[tata(a[k].y)]=tata(a[k].x);
        viz[k]=1;
        s+=a[k].c;
        k++;
    }
	
    printf("%d\n",s);
    printf("%d\n",n-1);
	
    for(int i=1;i<=m;i++)
        if(viz[i])
			printf("%d %d\n",a[i].x,a[i].y);
}
 
int main()
{
    int x,y,c;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
        apm();
    return 0;
}