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

using namespace std;

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

vector<int> v;

int x[400100],y[400100],c[400100],g[400100],ind[400100];
int n,m,cost;

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()
{
    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'<<v.size()<<'\n';

    for(int i=0;i<v.size();i++)
        fout<<y[v[i]]<<' '<<x[v[i]]<<'\n';
}