#include <bits/stdc++.h>

#define NMAX 200005
#define MMAX 400005

using namespace std;

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

int p[NMAX],n,m;
long long int C;

struct noduri
{
    int x,y,cost;
} v[MMAX];

int parinte(int nod)
{

    if(p[nod]==nod)
        return nod;
    return p[nod]=parinte(p[nod]);
}
bool cmpf(noduri i,noduri j)
{
	return(i.cost < j.cost);
}
void unire(int vf1, int vf2)
{
    p[parinte(vf1)]=parinte(vf2);
}

void alocare()
{
    for(int i=1; i<=n; i++)
        p[i]=i;
}
int main()
{
    f>>n>>m;
    vector <pair<int,int> >Q;
    for(int i=1; i<=m; i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    alocare();
    sort(v+1,v+m+1,cmpf);
    for(int i=1; i<=m; i++)
        if(parinte(v[i].y)!=parinte(v[i].x ))
        {
            unire(v[i].x,v[i].y);
            C+=v[i].cost;
            Q.push_back(make_pair(v[i].x, v[i].y));
        }
    g<<C<<"\n";
    g<<Q.size()<<"\n";
    for(int i=0; i<Q.size(); i++)
        g<<Q[i].first<<" "<<Q[i].second<<"\n";
    return 0;
}