import java.io.*;
import java.util.*;
 
class FastScanner {
    private BufferedReader br;
    private StringTokenizer st;
 
    public FastScanner(InputStream stream) {
        br = new BufferedReader(new InputStreamReader(stream));
    }
 
    private String next() {
        while (st == null || !st.hasMoreTokens()) {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (line == null)
                return null;
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
 
    public long nextLong() {
        return Long.parseLong(next());
    }
 
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

class Edge implements Comparable<Edge> {
	public int from;
	public int to;
	public int cost;
	
	public Edge(final int from, final int to, final int cost) {
		this.from = from;
		this.to = to;
		this.cost = cost;
	}
	
	public int compareTo(final Edge other) {
		if (cost < other.cost)
			return -1;
		if (other.cost < cost)
			return 1;
		if (from < other.from)
			return -1;
		if (other.from < from)
			return 1;
		if (to < other.to)
			return -1;
		if (other.to < to)
			return 1;
		return 0;
	}
}

class DisjointDataSets {
	private static final int NIL = -1;
	
	private int[] fathers;
	private int[] ranks;
	
	public DisjointDataSets(final int size) {
		fathers = new int[size];
		Arrays.fill(fathers, NIL);
		ranks = new int[size];
	}
	
	private int find(final int x) {
		if (fathers[x] == NIL)
			return x;
		return fathers[x] = find(fathers[x]);
	}
	
	public boolean merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return false;
		if (ranks[x] < ranks[y]) {
			int auxiliary = x;
			x = y;
			y = auxiliary;
		}
		fathers[y] = x;
		ranks[x] = Math.max(ranks[x], ranks[y]);
		return true;
	}
}
 
public class Main {
    private static List<Edge> Kruskal(final int vertexCount, final List<Edge> edges) {
    	Collections.sort(edges);
    	DisjointDataSets sets = new DisjointDataSets(vertexCount);
    	List<Edge> minimumSpanningTree = new ArrayList<Edge>();
    	for (Edge e: edges)
    		if (sets.merge(e.from, e.to))
    			minimumSpanningTree.add(e);
    	return minimumSpanningTree;
    }
     
    public static void main(String[] args) throws IOException {
        FastScanner reader = new FastScanner(new FileInputStream("apm.in"));
        int vertexCount = reader.nextInt();
        int edgeCount = reader.nextInt();
        List<Edge> edges = new ArrayList<Edge>();
        for (; edgeCount > 0; --edgeCount) {
            int x = reader.nextInt() - 1;
            int y = reader.nextInt() - 1;
            int c = reader.nextInt();
            edges.add(new Edge(x, y, c));
        }
        
        List<Edge> minimumSpanningTree = Kruskal(vertexCount, edges);
        int minimumSpanningTreeCost = 0;
        for (Edge e: minimumSpanningTree)
        	minimumSpanningTreeCost += e.cost;
         
        PrintWriter writer = new PrintWriter("apm.out");
        writer.write(minimumSpanningTreeCost + "\n" + minimumSpanningTree.size() + "\n");
        for (Edge e: minimumSpanningTree)
        	writer.write((e.from + 1) + " " + (e.to + 1) + "\n");
        writer.close();
    }
}