#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct cell{
       int a,b,c;
       };

int getParent(int a, int parent[])
{
    if( parent[a] == a ) return a;
    return parent[a] = getParent( parent[a], parent );
}

bool comp(cell x, cell y)
{
	return x.c < y.c;
}

int main()
{
	FILE *f = fopen("apm.in","r");
	FILE *g = fopen("apm.out","w");
    int n ,m;

	fscanf(f, "%d%d", &n, &m);
    cell edges[m]; 
	int p[n+1];
    for(int i = 1; i <= n; i++) 
		p[i] = i;
      
    for(int i = 0; i < m; i++){
		fscanf(f, "%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c);
	}
    sort(edges, edges+m, comp);
    
    cell res[n+2];
    int sum=0, k=0; 
	for(int i=0; i<m; i++){
        if( getParent(edges[i].a, p) != getParent(edges[i].b, p) ){
            p[p[edges[i].a]] = p[edges[i].b];
            sum += edges[i].c;
			res[k] = edges[i];
			k++;
		}
    }        

	fprintf(g, "%d\n%d\n", sum, n-1);
    for(int i=0; i<n-1; i++)
		fprintf(g, "%d %d\n", res[i].b, res[i].a);
}