#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
//-------------------------------------------------------------
//Variabile globale
struct
{
    int x,y;
}st[200001];
int n,v[200001],grad[200001],nr;
priority_queue<pair<int,pair<int,int>>>q;
//-------------------------------------------------------------
//Functii
void citire();
void rezolva();
void uneste(int,int);
bool cauta(int,int);
//-------------------------------------------------------------
int main()
{
    citire();
    rezolva();
    return 0;
}
//-------------------------------------------------------------
bool cauta(int a,int b)
{
	int a2 = a;
	while(v[a2] != a2)
		a2 = v[a2];
	int b2 = b;
	while(v[b2] != b2)
		b2 = v[b2];
	if(a2 == b2)
	{
		return true;
		while(a != a2)
		{
			int a3 = a;
			a = v[a];
			v[a3] = a2;
		}
		while(b != a2)
		{
			int b3 = b;
			b = v[b];
			v[b3] = a2;
		}
	}
	else
    {
        return false;
        while(a != a2)
		{
			int a3 = a;
			a = v[a];
			v[a3] = a2;
		}
		while(b != b2)
		{
			int b3 = b;
			b = v[b];
			v[b3] = b2;
		}
    }
}
//-------------------------------------------------------------
void uneste(int a,int b)
{
	int a2 = a;
	while(v[a2] != a2)
		a2 = v[a2];
	int b2 = b;
	while(v[b2] != b2)
		b2 = v[b2];
	if(grad[a2] < grad[b2])
	{
		swap(a2,b2);
		swap(a,b);
	}
	grad[a2] += grad[b2];
	while(a != a2)
	{
		int a3 = a;
		a = v[a];
		v[a3] = a2;
	}
	while(b != b2)
	{
		int b3 = b;
		b = v[b];
		v[b3] = a2;
	}
	v[b2]=a2;
}
//-------------------------------------------------------------
void rezolva()
{
    for(int i = 1;i <= n;++i)
    {
        v[i] = i;
        grad[i] = 1;
    }
    int sum = 0;
    while(!q.empty())
    {
        int cost,x,y;
        cost = -q.top().first;
        x = q.top().second.first;
        y = q.top().second.second;
        q.pop();
        if(!cauta(x,y))
        {
            uneste(x,y);
            sum += cost;
            st[++nr].x = x;
            st[nr].y = y;
        }
    }
    g << sum << '\n' << n - 1 << '\n';
    for(int i = 1;i < n;++i)
        g << st[i].x << " " << st[i].y <<'\n';
}
//-------------------------------------------------------------
void citire()
{
    int m;
    f >> n >> m;
    while(m--)
    {
        int a,b,c;
        f >> a >> b >> c;
        q.push({-c,{a,b}});
    }
}