#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int n,m,xx,yy,i,Cost,conect,a,b,COST=0;

struct str
{
    int x,y,c;
};
vector<str> G;
str z;
int r[200003],t[200003];
bool apar[400003];

bool cmp(str  x,str y)
{
    if(x.c<y.c) return true;
    return false;

}

void unite(int x,int y)
{
    if(r[x]<r[y])
    t[x]=y;
    else t[y]=x;

    if(r[x]==r[y]) r[x]++;


}

int find(int x)
{
    int z=x,y;
    while(t[x]!=x)
    x=t[x];

    while(t[z]!=z)
    {
        y=z;
        z=t[z];
        t[y]=x;
    }

    return x;

}


int main()
{
    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",&xx,&yy,&Cost);
        z.x=xx;
        z.y=yy;
        z.c=Cost;
        G.push_back(z);
    }

    for(i=1;i<=n;++i)
    r[i]=0,t[i]=i;

    sort(G.begin(),G.end(),cmp);

    COST=0;conect=1;
    for(i=0;i<m && conect<n;++i)
    {
        a=find(G[i].x);
        b=find(G[i].y);

        if(a!=b)
        {
            unite(a,b);
            COST+=G[i].c;
            conect++;
            apar[i]=true;
        }

    }

    printf("%d\n%d\n",COST,n-1);

    for(i=0;i<m;++i)
    if(apar[i]) printf("%d %d\n",G[i].x,G[i].y);


    return 0;
}