#include<fstream>
#include<algorithm>
#include<vector>

#define pb push_back

using namespace std;

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

const int maxn=400100;

int GR[maxn], X[maxn], Y[maxn], C[maxn];

int N, M, ANS, IND[maxn];

vector <int> VANS;

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);
}

bool cmpf(int i, int j)
{
    return(C[i]<C[j]);
}

int main()
{
    f >> N >> M;
    for (int i=1; i<=M; i++)
    {
        f >> X[i] >> Y[i] >> C[i];
        IND[i]=i;
    }
    for (int i=1; i<=N; i++)
    {
        GR[i]=i;
    }
    for (int i=1; i<=N; i++)
    {
        GR[i]=i;
    }
    sort(IND+1, IND+M+1, cmpf);
    for (int i=1; i<=M; i++)
    {
        if (grupa(X[IND[i]])!=grupa(Y[IND[i]]))
        {
            ANS+=C[IND[i]];
            reuniune(X[IND[i]], Y[IND[i]]);
            VANS.pb(IND[i]);
        }
    }
    g << ANS << '\n';
    g << N-1 << '\n';
    for (int i=0; i<N-1; i++)
    {
        g << X[VANS[i]] <<" "<< Y[VANS[i]] << '\n';
    }
    return 0;
}