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

using namespace std;

    ifstream fin("apm.in");
    ofstream fout("apm.out");

vector<int>v;

int x[400100],y[400100],c[400100],g[400100];

int b[400100],ind[400100];

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

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

bool cmp(int i,int j)
{
    return (c[i] < c[j]);
}

int main()
{
    int n,m,cost=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }

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

    sort(ind+1,ind+m+1,cmp);

    for(int i = 1;i <= m; i++)
    {
        if (grupa(x[ind[i]]) != grupa(y[ind[i]]))
        {
            cost += c[ind[i]];
            reuniune(x[ind[i]],y[ind[i]]);
            v.push_back(ind[i]);
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        fout<<x[v[i]]<<' '<<y[v[i]]<<'\n';
}