#include<cstdio>
#include<algorithm>
#include<vector>
#define NMAX 400001
using namespace std;
int x[NMAX],y[NMAX],c[NMAX],mul[NMAX],ind[NMAX];
int n,m;
vector<int>sol;
int cmp(int r,int q)
{
    return (c[r]<c[q]);
}
int find(int i)
{
    if (mul[i]==i) return i;
    mul[i]=find(mul[i]);
    return mul[i];
}
void reuneste(int i,int j)
{
    mul[find(i)]=find(j);
}
int main()
{
    int i;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
        ind[i]=i;
    }
    for (i=1;i<=n;++i) mul[i]=i;
    sort(ind+1,ind+m+1,cmp);
    int sum=0;
    for (i=1;i<=m;++i)
    {
        if (find(x[ind[i]])!=find(y[ind[i]]))
        {
            sum+=c[ind[i]];
            reuneste(x[ind[i]],y[ind[i]]);
            sol.push_back(ind[i]);
        }
    }
    printf("%d\n",sum);
    vector<int>::iterator it;
    printf("%d\n",sol.size());
    for(it=sol.begin();it!=sol.end();++it)
    {
        printf("%d %d\n",x[*it],y[*it]);
    }
    return 0;
}