#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define mp make_pair
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int maxn=400005;
struct apm
{
    int x,y,cost;
}APM[maxn];
vector <pair <int,int> > Gans;
int N,M,X[maxn],Y[maxn],C[maxn];
int GRUP[maxn],nr_grup[maxn];
int cmp (apm a, apm b)
{
    if(a.cost<b.cost)
        return 1;
    return 0;
}
int grupa(int x)
{
    int R, y;
    for (R = x; GRUP[R] != R; R = GRUP[R]);

    while(GRUP[x]!=x)
    {
        y = GRUP[x];
        GRUP[x] = R;
        x = y;
    }
    return R;
}
void reunire(int x, int y)
{
    if (nr_grup[x] > nr_grup[y])
        GRUP[y] = x;
    else GRUP[x] = y;

    if (nr_grup[x] == nr_grup[y]) nr_grup[y]++;
}
int main()
{
    int i,ans=0;
    f>>N>>M;
    for (i=1;i<=M;i++)
    {
        f>>APM[i].x>>APM[i].y>>APM[i].cost;
    }
    sort(APM+1,APM+M+1,cmp);

    for (int i=1;i<=N;i++) {nr_grup[i]=1;GRUP[i]=i;}

    for (i=1;i<=M;i++)
    {
        if (grupa(APM[i].x) != grupa(APM[i].y) )
        {
            reunire(grupa(APM[i].x),grupa(APM[i].y));
            ans+=APM[i].cost;
            Gans.push_back(mp(APM[i].x,APM[i].y));
        }
    }
    g<<ans<<'\n';
    g<<N-1<<'\n';
    for (i=0;i<N-1;i++)
        g<<Gans[i].first<<" "<<Gans[i].second<<'\n';


}