#define NMAX 200001
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[NMAX], l[NMAX], n,nr,costmin;
struct muchie
{
    int x,y;
    int cost;
    friend bool operator > (const muchie&, const muchie&);
};
priority_queue <muchie, vector<muchie>, greater<muchie> > coada;
vector<muchie> sol;
bool operator > (const muchie& m1, const muchie& m2)
{
    ///operator
    return m1.cost>m2.cost;
}
int f(int x)
{
	int r,y;
	r=x;
	while(t[r]!=r) r=t[r];
    y=x;
    int tata;
	while(y!=r)
	{
		tata=t[y];
		t[y]=r;
		y=tata;
	}
	return r;
}
void unire(int x, int y)
{
	if (l[x]>l[y])
		t[y]=x;
    else
        t[x]=y;
	if (l[x]==l[y])
        l[y]++;
}
int main()
{
    int c1,c2;
    fin>>n>>nr;
    for(int i=1;i<=n;i++)
        t[i]=i;
    muchie m;
    for(int i=1;i<=nr;i++)
    {
        fin>>m.x>>m.y>>m.cost;
        coada.push(m);
    }
    while(sol.size()<n-1)
    {
        m=coada.top(); coada.pop();
        c1=f(m.x); c2=f(m.y);
        if(c1!=c2)
        {
            costmin+=m.cost; sol.push_back(m);
            unire(c1,c2);
        }
    }
    fout<<costmin<<'\n'<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)
    {
        fout<<sol[i].y<<' '<<sol[i].x<<'\n';
    }
    return 0;
}