#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
 
using namespace std;
 
#define NMAX 200005
#define CMAX 1005 
 
int N, M;
 
struct neigh{
	int i, w;
	neigh(int i, int w)
	{
		this->i = i, this->w = w;
	}
};
 
struct muchie
{
	int x, y;
}; 
 
vector<neigh> v[NMAX];
 
void citire(){
    FILE * f = fopen("apm.in", "rt");
    fscanf(f, "%d %d", &N, &M);
    int x, y, w;
	for(int i = 0; i < M; ++i){        
		fscanf(f, "%d %d %d", &x, &y, &w);
		--x, --y;
        neigh n1(y,w), n2(x, w);
		v[x].push_back(n1);
		v[y].push_back(n2);
    }
    fclose(f);
}

int A[NMAX], Heap[NMAX], Pos[NMAX], t = 0, n = 0;

int getLeft(int p){ return 2 * p + 1;}
int getRight(int p){ return 2 * p + 2;}
int getParent(int p){return (p-1)/2;}

int getMin()
{
	return A[Heap[0]];
}

void up(int p)
{
	while(p > 0 && A[Heap[p]] < A[Heap[getParent(p)]]){
		swap(Heap[p], Heap[getParent(p)]);
		Pos[Heap[p]] = p;
		Pos[Heap[getParent(p)]] = getParent(p);
		p = getParent(p);
	}
}

void down(int p)
{
	int son;
	do{
		son = -1;
		if(getLeft(p) < n)
		{
			son = getLeft(p);
			if(getRight(p) < n && A[Heap[son]] > A[Heap[getRight(p)]])
				son = getRight(p);
		}
		
		if(son != -1)
		{
			if(A[Heap[son]] < A[Heap[p]])
			{
				swap(Heap[son], Heap[p]);
				Pos[Heap[son]] = son;
				Pos[Heap[p]] = p;
				p = son;
			}
			else
			{
				son = -1;
			}
		}
		
	}while(son != -1);
}


void insert(int x)
{
	A[t] = x, Pos[t] = n, Heap[n] = t; 
	++t, ++n;
	up(n-1);
}

void del(int x)
{
	int pos = Pos[x];
    A[x] = -CMAX;

	up(pos);

	Heap[0] = Heap[n-1];
	Pos[Heap[0]] = 0;
	
	n--;
	
	down(0);
}

void update(int p, int x)
{
	A[p] = x;
	int pos = Pos[p];
	if(pos > 0 && A[Heap[pos]] < A[Heap[getParent(pos)]])
		up(pos);
	else
		down(pos);
}
  
int main(){
    citire();
	
	bool taken[NMAX];
	int	pred[NMAX];
	
	for(int i = 0; i < N; ++i)
	{
		insert(CMAX);
		taken[i] = false;
	}

	update(0, 0);
	pred[0] = 0;
	
	int total = 0;
	
	vector<muchie> muchii;
	
	while(n > 0)
	{
		int m = getMin();
		int p = Heap[0];
		if(!taken[p]){
			taken[p] = true;
			total += m;
			muchie much;
			much.x = p, much.y = pred[p];
			muchii.push_back(much);
			//for(int i = 0; i < N; ++i)
			//	cout << pred[i] << " ";
			//cout << endl;
			//cout << "added: " << p << "," << pred[p] << endl;
			// update all its friends
			for(unsigned j = 0; j < v[p].size(); ++j)
				if(!taken[v[p][j].i] && A[v[p][j].i] > v[p][j].w){
					update(v[p][j].i, v[p][j].w);
					pred[v[p][j].i] = p;
			//		cout << "pred[" << v[p][j].i << "] = " << p << endl;
				}
		}
		del(p);
	}
	
	
	FILE * f = fopen("apm.out", "wt");
	
	fprintf(f, "%d\n", total);
	fprintf(f, "%d\n", muchii.size() - 1);
	
	for(unsigned i = 1; i < muchii.size(); ++i)
		fprintf(f, "%d %d\n", muchii[i].x + 1, muchii[i].y  + 1);
    return 0;
}