import java.util.Scanner;
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main
{
	public static void main(String args[]) throws FileNotFoundException 
	{
		int N,M;
		
		Scanner scanner = new Scanner(new File("apm.in"));
		N = scanner.nextInt();
		M = scanner.nextInt();

		Edge[] edges = new Edge[M];
		for(int i=0;i<M;i++)
		{
			int a,b,c;
			a = scanner.nextInt()-1;
			b = scanner.nextInt()-1;
			c = scanner.nextInt();
			edges[i] = new Edge(a,b,c);
		}		
		Arrays.sort(edges,Edge.EdgeComparator);
		int cost = 0;
		int nodes = 0;
		DisjointSet set = new DisjointSet(N);
		String str = new String();
		for(int i=0;i<M;i++)
		{
			int a = edges[i].from;
			int b = edges[i].to;
			// System.out.println(i);
			if(!set.Find(a,b))
			{
				set.Union(a,b);
				cost += edges[i].value;
				str += (a+1)+" "+(b+1)+"\n";
				nodes++; 
			}
		}
		String pre = cost+"\n"+nodes+"\n";
		String out = pre+str;
		try
		{
			write_out(out);
		}catch(IOException e){}
		// System.out.println(str);
	}

	public static void write_out(String out) throws IOException
	{
		PrintWriter pw = new PrintWriter(new FileWriter("apm.out"));
		pw.write(out);
		pw.close();
	}

	private static class Edge
	{
		int from,to,value;
		private Edge(int from,int to,int value)
		{
			this.from = from;
			this.to = to;
			this.value = value;
		}

		private int CompareTo(Edge compareEdge)
		{
			return this.value - compareEdge.value;
		}


		public static Comparator<Edge> EdgeComparator
					 = new Comparator<Edge>()
		{
			public  int compare(Edge a, Edge b)
			{
				return a.CompareTo(b);
			}
		};
	}

	private static class DisjointSet
	{
		int[] arr;
		private DisjointSet(int N)
		{
			int[] arr = new int[N];
			this.arr = arr;
			for(int i=0;i<N;i++)
				arr[i] = i;
		}

		private int Root(int k)
		{
			while(arr[k] != k)
				k = arr[k];
			return k;
		}

		private void Union(int i, int j)
		{
			arr[Root(i)] = arr[Root(j)];
		}

		private boolean Find(int i,int j)
		{
			return (Root(i) == Root(j));
		}

	}
}