#include <fstream>
#include <algorithm>
using namespace std;
fstream fin("apm.in");
ofstream fout("apm.out");
int t[200000],h[200000];
int FindSet(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
void UnionSet(int x,int y)
{
    if(h[x]==h[y])
    {
        t[y]=x;
        h[x]++;
    }
    else
        if(h[x]>h[y])
            t[y]=x;
        else
            t[x]=y;
}
struct AP{int x,y,z;bool w;};
bool cmp(AP a,AP b)
{
    return a.z<b.z;
}
AP g[400000];
int main()
{
    int n,c,u,v,m,i,cnt,tx,ty,cost=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v>>c;
        g[i].x=u;g[i].y=v;g[i].z=c;
    }
    sort(g+1,g+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    i=1;
    while(i<=m&&cnt<n-1)
    {
        tx=FindSet(g[i].x);
        ty=FindSet(g[i].y);
        if(tx!=ty)
        {
            UnionSet(tx,ty);
            g[i].w=1;
            cnt++;
            cost=cost+g[i].z;
        }
         i++;

    }
    fout<<cost<<"\n"<<n-1<<"\n";
    cnt=1;
    for(i=1;i<=m;i++)
    {
        if(cnt==n-1)
        {
            fout<<g[i].y<<" "<<g[i].x;
            break;
        }

        if(g[i].w==1)
        {
            fout<<g[i].y<<" "<<g[i].x<<"\n";
            cnt++;
        }

    }

    return 0;
}