#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct drum {int c,p,o;};
struct noduri{int x,y;};
int n,m,x,y,cost,t[200002],n1,n2,l;
drum nd;
noduri nd1;
vector <noduri> sol;
drum a[400001];

int tata(int nod)
{
    if(t[nod]!=nod) t[nod]=tata(t[nod]);
    return t[nod];
}

bool cmp(drum i,drum j)
{
    return (i.c<j.c);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d\n",&x,&y,&cost);
        nd.c=cost;
        nd.p=x;
        nd.o=y;
        a[l]=nd;
        l++;
    }
    cost=0;
    sort(a,a+l,cmp);
    for(int i=0;i<n;i++) t[i]=i;
    for(int i=0;i<m;i++)
    {
        n1=a[i].p;
        n2=a[i].o;
        if(tata(n1)!=tata(n2))
        {
            cost+=a[i].c;
            nd1.x=n1;
            nd1.y=n2;
            sol.push_back(nd1);
            t[t[n2]]=t[n1];
        }
    }
    printf("%d\n%d\n",cost,sol.size());
    for(int i=0;i<sol.size();i++) printf("%d %d\n",sol[i].x,sol[i].y);
    fclose(stdin);fclose(stdout);return 0;
}