#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

struct edge{int x,y,c;};
edge edges[400010];

int ans[400010];
int dad[200010];

bool cmp(edge x,edge y)
{
    return x.c<y.c;
}

int find_dad(int x)
{
    if(x==dad[x])
        return x;
    dad[x]=find_dad(dad[x]);
    return dad[x];
}

int main()
{
    srand(time(0));
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,nr=0,s=0,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&edges[i].x,&edges[i].y,&edges[i].c);
    for(i=1;i<=n;i++)
        dad[i]=i;
    sort(edges+1,edges+m+1,cmp);
    for(i=1;i<=m,nr!=n-1;i++)
    {
        x=find_dad(edges[i].x);
        y=find_dad(edges[i].y);
        if(x!=y)
        {
            nr++;
            ans[nr]=i;
            s+=edges[i].c;
            if(rand()%2==0)
                dad[x]=y;
            else
                dad[y]=x;
        }
    }
    printf("%d\n%d\n",s,n-1);
    for(i=1;i<=n-1;i++)
        printf("%d %d\n",edges[ans[i]].x,edges[ans[i]].y);
    return 0;
}