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

const int NMAX = 100020;

int tata[NMAX], rg[NMAX];
int n, m;
int X[NMAX], Y[NMAX], C[NMAX];
vector<int> indice;
vector<int> arb;
void MakeSet(int n)
{
    for(int i = 0 ; i <= n; i++)
    {
        tata[i] = i;
        rg[i] = 0;
    }
}

int find(int x)
{
    int R, y;
    //ma deplasez in sus pe arbore pana dau de un nod care e propriul tata
    for(R = x; tata[R] != R; R = tata[R]);

    //fac compresie de drumuri
    while(tata[x] != x)
    {
        y = tata[x];
        tata[x] = R;
        x = y;
    }
    return R;
}

bool unite(int x, int y)
{
    if(x == y)
        return false;
    if(rg[x] > rg[y])
        tata[y] = x;
    else
        tata[x] = y;
    if(rg[x] == rg[y])
        rg[y]++;
    return true;
}

bool cmp(int x, int y)
{
    return C[x] < C[y];
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int cost = 0;
    f>>n>>m;
    MakeSet(n);
    indice.push_back(-1);
    for(int i = 1; i <= m; i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        X[i] = x;
        Y[i] = y;
        C[i] = c;
        indice.push_back(i);
    }
    sort(indice.begin()+1, indice.begin()+m+1, cmp);
    for(int i = 1; i <= m; i++)
        {
            if(unite(find(X[indice[i]]), find(Y[indice[i]])))
            {
                arb.push_back(indice[i]);
                cost += C[indice[i]];
            }
        }
    g<<cost<<'\n'<<n-1<<'\n';
    for(unsigned int i = 0; i < arb.size(); i++)
        g<<X[arb[i]]<<' '<<Y[arb[i]]<<'\n';
    return 0;
}