import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
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) && 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));
			}
			if(counter == (n-1)) break;
		}
		File filewrite = new File ("apm.out");
		FileWriter writer = new FileWriter(filewrite);
		writer.write(String.valueOf(sum));
		writer.write("\r\n");
		writer.write(String.valueOf(counter));
		writer.write("\r\n");
		for(Main search : result)
		{
			writer.write(String.valueOf(search.st) + " " + String.valueOf(search.dr) + "\r\n");
		}
		writer.flush();
		keyboard.close();
		
	}

}