import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

class CostCmp implements Comparator<Edge>{
	public int compare(Edge e1, Edge e2){
		if(e1.cost < e2.cost){
			return -1;
		}
		if(e1.cost > e2.cost){
			return 1;
		}
		return 0;
	}
}


public class Main {

	

	public static int N, M, costAMA; 
	public static int  []d = new int [10000];
	public static ArrayList<Edge> E = new ArrayList<>();
	public static ArrayList<Edge> E1 = new ArrayList<>();
	public static int []sol = new int[100];
	
	public static Edge [][]matrix = new Edge[100][100];

	
	public static int p(int x){
		if(d[x] != x)
			d[x] = p(d[x]);
		return d[x];
	}
	
	public static void reunion(int x, int y){
		d[p(x)] = p(y);
	}
	
	public static void Kruskal(){
		
		
		Comparator<Edge> cmp = new CostCmp();
		
		Collections.sort(E, cmp);
		
		for(int i = 1; i <= N; i++){
			d[i] = i;
		}
		
		int k = 0;
		for(int i = 0; i < M && k != N-1; i++){
			if(p(E.get(i).x) != p(E.get(i).y)){
				costAMA += E.get(i).cost;
				sol[k] = i;
				k++;
				reunion(p(E.get(i).x), p(E.get(i).y));
			}
			else{
				E1.add(E.get(i));
			}
		}
		//System.out.println("nr de sol "+ k);
	}
	
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub

		

	    	Scanner reader = new Scanner(new FileInputStream("apm.in"));
	            
	       
	        
	        N = reader.nextInt();
	        M = reader.nextInt();
	        
	        
	        for(int k = 0; k < M; k++){

	        	 int i = reader.nextInt();
	        	 int j = reader.nextInt();
	        	 int cost = reader.nextInt();
		        E.add(new Edge(i,j,cost));
	        }
	       
	        Kruskal();
	        
	        PrintWriter writer = new PrintWriter("apm.out");
	        writer.write(String.valueOf(costAMA) + "\n");
	        int nr = N-1;
	        writer.write(String.valueOf(nr));
	        for(int i = 0; i < N-1; i++){
	        	writer.write(E.get(i).x + " ");
	        	writer.write(E.get(i).y + "\n");
	        }


	}

}