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

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> v;

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]]);
            v.push_back(IND[i]);
        }
    }
    g << ANS << '\n';
    g << N - 1 << '\n';
    for(int i = 0; i < N - 1; ++i)
        g << Y[v[i]] << ' ' << X[v[i]] << '\n';
    return 0;
}