#include <bits/stdc++.h>
using namespace std;
struct dd
{
    int x,y,cost;
};
bool cmp(dd a,dd b)
{
    if(a.cost==b.cost)
    {
        if(a.x==b.x)return a.y<b.y;
        return a.x<b.x;
    }
    return a.cost<b.cost;
}
dd v[100005];
int h[100005],t[100005];
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[x]=y;
    if(h[y]<h[x])t[y]=x;
    if(h[x]==h[y])h[x]++,t[y]=x;
}
int fr[100005];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int m,n,i,j;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
    }
    sort(v+1,v+n+1,cmp);
    int sum=0;
    for(i=1;i<=m;i++)h[i]=1,t[i]=i;
    for(i=1;i<=n;i++)
    {
        int a=findset(v[i].x),b=findset(v[i].y);
        if(a!=b)
        {
            fr[i]=1;
            sum+=v[i].cost;
            unionset(a,b);
        }
    }
    cout<<sum<<"\n";
    cout<<m-1<<"\n";
    for(i=1;i<=n;i++)
        if(fr[i])
        cout<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}