#include<fstream>
#include<vector>
#include<algorithm>
#define pp 400100
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,cost,n,m,x[pp],y[pp],c[pp],t[pp],ord[pp];
vector<int> v;
int tata(int i)
{
    if(t[i]==i)
    return i;
    t[i]=tata(t[i]);
    return t[i];
}
void uneste(int i,int j)
{
    t[i]=j;
}
int cmp(int i,int j)
{
    return(c[i]<c[j]);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x[i]>>y[i]>>c[i];
        t[i]=i; ord[i]=i;
    }
    sort(ord+1,ord+m+1,cmp);
    for(i=1;i<=m;++i)
    {
        if(tata(x[i])!=tata(y[i]))
        {
            uneste(t[x[i]],t[y[i]]);
            v.push_back(ord[i]);
            cost+=c[ord[i]];
        }
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;++i)
    g<<x[v[i]]<<" "<<y[v[i]]<<'\n';
    return 0;
}