#include <fstream>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie { int x,y,c; } u[400001];
int N,M,arc[200001];

class DisjointSets {   
public:   
    DisjointSets (unsigned int size) : size(size), info(new Info[size])   
    { for (unsigned int i=0; i<size; ++i) info[i].parent = i, info[i].rank = 0; }   
    void unionSets (unsigned int x, unsigned int y);   
    unsigned int findSet (unsigned int x);   
private:   
    struct Info {   
        unsigned int parent;   
        unsigned int rank;   
    } *info;   
    unsigned int size;   
};

void DisjointSets::unionSets (unsigned int x, unsigned int y)   
{   
    unsigned int xRoot = findSet(x), yRoot = findSet(y);   
    if (info[xRoot].rank < info[yRoot].rank)   
        info[yRoot].parent = xRoot;   
    else if (info[xRoot].rank > info[yRoot].rank)   
        info[xRoot].parent = yRoot;   
    else if (xRoot != yRoot) {   
        info[yRoot].parent = info[xRoot].parent;   
        ++info[xRoot].rank;   
    }   
}   
unsigned int DisjointSets::findSet (unsigned int x)   
{   
    if (info[x].parent == x) return x;   
    info[x].parent = findSet(info[x].parent);   
    return info[x].parent;   
}

/* int partitionare (int s, int d)
{
//    int pivot = u[s+rand()%(d-s+1)].c;
    int pivot = u[s].c;
    int i=s,j=d;
    Muchie aux;
    while (i < j) {
          cout << i << " " << j << " " << "\n";
          while (u[i].c<pivot) i++;
          while (u[j].c>pivot) j--;
          while (u[i].c == u[j].c) { i++; j--; }
          if (i < j) { aux=u[i]; u[i] = u[j]; u[j] = aux; }
    }
    return i;
}*/
int partitionare (int s, int d)
{
    int i=s,j=d,pi=0,pj=1,aux2;
    Muchie aux;
    while (i<j) {
       if (u[i].c > u[j].c) { aux=u[i]; u[i] = u[j]; u[j] = aux; aux2=pi; pi=pj;pj=aux2; }
       i+=pi;
       j-=pj;
    }
    return i;
    
}

void quicksort (int x, int y)
{
    if (x < y) {
       cout << "quicksort(" << x << "," << y << ")" << '\n';
       int m = partitionare(x,y);
       cout << "  - returneaza " << m << '\n';
       quicksort(x, m-1);
       quicksort(m+1, y);
    }
}

int main ()
{
    srand(time(NULL));
	int i, j;
	in >> N >> M;
	for (i=1; i<=M; i++)
		in >> u[i].x >> u[i].y >> u[i].c;
	in.close();
	int k=1;
	Muchie aux;
	quicksort(1, M);
	i=1;
	long long cost = 0;
	DisjointSets p(M);
	while (k < N) {
        if (p.findSet(u[i].x) != p.findSet(u[i].y)) {
			arc[k] = i;
			cost += u[i].c;
			p.unionSets(u[i].x, u[i].y);
			k++;
		}
		i++;
	}

	out << cost << '\n';
	out << N-1 << '\n';
	for (i=1; i<N; i++) out << u[arc[i]].x << ' ' << u[arc[i]].y << '\n';
	out.close();
	return 0;
}