#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

#define MAXN 200005


struct muchie
{
    int x,y,cost;
}aux,crt;

vector<muchie> v,rasp;
int n,m,i,j,sum;
int GR[MAXN];

bool cmp(muchie A, muchie B)
{
    return A.cost < B.cost;
}

int grupa(int i)
{
    if(GR[i] == i) return i;
    GR[i]= grupa(GR[i]);
    return GR[i];
}

void reuniune(int i, int j)
{
    GR[grupa(i)] = grupa(j);
}

int main()
{
    cin>>n>>m;

    for(i=1; i<=m; i++)
    {
        cin>>aux.x>>aux.y>>aux.cost;
        v.push_back(aux);
    }

    for(i=1; i<=n; i++)
        GR[i] = i;

    sort(v.begin(), v.end(), cmp);
    for(i=0; i<m; i++)
    {
        crt = v[i];
        if(grupa( crt.x ) != grupa( crt.y ))
        {
            reuniune ( GR[ crt.x ], GR[ crt.y ] );
            sum += v[i].cost;
            rasp.push_back(crt);
        }
    }
    cout<<sum<<"\n"<<n-1<<"\n";
    for(i=0; i<rasp.size(); i++)
        cout<<rasp[i].x<<" "<<rasp[i].y<<"\n";

}