#include <fstream>
#include <queue>
#define NMAX 200001
using namespace std;

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

struct muchie{
    int x,y;
    int cost;
    friend bool operator > (const muchie&, const muchie&);
};
bool operator > (const muchie& m1, const muchie& m2)
{
    return m1.cost>m2.cost;
}

priority_queue <muchie, vector<muchie>, greater<muchie> > H;
vector<muchie> sol;

int t[NMAX], l[NMAX], n,nr,costmin;

void Citire();

int fnd(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;
        H.push(m);
    }
    while(sol.size()<n-1) //cat timp nu am selectat cele n-1 muchii
    {
        //extrag din H muchia de cost minim
        m=H.top(); H.pop();
        //determin comp conexe din care fac parte
        //extremitatile muchiei selectate m
        c1=fnd(m.x); c2=fnd(m.y);
        if(c1!=c2) //m nu formeaza cicluri cu muchiile selectate
        {
            //selectez aceasta muchie
            costmin+=m.cost; sol.push_back(m);
            //unific componentele conexe ale extremitatilor
            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;
}