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

#define NDIM 200005
#define MDIM 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int i,n,m,sol,x[MDIM],y[MDIM],c[MDIM],poz[MDIM],G[NDIM];
vector <int> v;
bool cmpf(int x,int y)
{
    return (c[x]<c[y]);
}

int grup(int i)
{
    if(G[i]==i)
        return i;
    G[i]=grup(G[i]);
    return G[i];
}
void adaug(int x,int y)
{
    G[grup(x)]=grup(y);
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        poz[i]=i;
    }
    for(i=1;i<=n;i++)
        G[i]=i;
    sort(poz+1,poz+m+1,cmpf);
    for(i=1;i<=m;i++)
    {
        if(grup(x[poz[i]])!=grup(y[poz[i]]))
        {
            sol+=c[poz[i]];
            adaug(x[poz[i]],y[poz[i]]);
            v.push_back(poz[i]);
        }
    }
    fout<<sol<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<x[v[i]]<<' '<<y[v[i]]<<'\n';
    return 0;
}