import java.io.File;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

 public class Main implements Comparator<Main> {
	
	int st;
	int dr;
	int cost;
	
	static int[] father = new int[200002];
	static ArrayList<Main> muchii = new ArrayList<Main>();
	static ArrayList<Main> result = new ArrayList<Main>();
	
	public Main(int x, int y, int z)
	{
		this.st = x;
		this.dr = y;
		this.cost = z;
	}
	
	public Main()
	{
		
	}
	
	public int compare(Main a, Main b)
	{
		return a.cost - b.cost;
	}
	static int find(int x)
	{
		if(x == father[x]) return x;
		else
		{
			father[x] = find(father[x]);
			return father[x];
		}
		
	}
	
	static void union(int x, int y)
	{
		int i = find(x);
		int j = find(y);
		father[i] = j;
	}
	
	public static void main(String[] args) 
			throws Exception
	{
		File file = new File ("apm.in");
		Scanner keyboard = new Scanner(file);
		int n = keyboard.nextInt();
		int m = keyboard.nextInt();
		for(int i=1;i<=m;i++)
		{
			int x = keyboard.nextInt();
			int y = keyboard.nextInt();
			int z = keyboard.nextInt();
			father[x] = x;
			father[y] = y;
			muchii.add(new Main(x,y,z));
		}
		Collections.sort(muchii, new Main());
		int sum = 0;
		int counter = 0;
		for(Main search : muchii)
		{
			if(counter == (n-1)) break;
			if(find(search.st) != find(search.dr))
			{
				counter ++;
				union(search.st, search.dr);
				sum += search.cost;
				result.add(new Main(search.st, search.dr, search.cost));
			}
		}
		FileWriter writer = new FileWriter("apm.out");
		PrintWriter out = new PrintWriter(writer);
		out.println(sum);
		out.println(counter);
		for(Main search : result)
		{
			out.print(search.st);
			out.print(" ");
			out.println(search.dr);
		}
		writer.flush();
		keyboard.close();
		
	}

}