#include <vector>
# include <algorithm>
# include <cstdio>
 
using namespace std;
 
vector < pair <int, pair <int, int> > > l;
int t[200010],i,x,y,c,nod,sum,nr,n,m;
struct {int xx; int yy;} b[200010];
 
int radx(int nod)
{
    if (t[nod]!=nod)
        t[nod]=radx(t[nod]);
    return t[nod];
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        l.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(l.begin(),l.end());
    for (i=1; i<=n; i++)
    {
        t[i]=i;
    }
    nr=0;
    for (i=0; i<l.size() && nr<=n-1; i++)
    {
        x=l[i].second.first;
        y=l[i].second.second;
        c=l[i].first;
        if (radx(x)!=radx(y))
        {
            sum+=c;
            b[++nr].xx=x; b[nr].yy=y;
            t[t[y]]=t[x];
        }
    }
    printf("%d\n",sum);
    printf("%d\n",nr);
    for (i=1; i<=nr; i++)
        printf("%d %d\n",b[i].xx, b[i].yy);
    return 0;
}