#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct dd
{
    int x,y,z;
}t;
bool cmp(dd a,dd b)
{
    if(a.z==b.z)return a.x<b.x;
    return a.z<b.z;
}
dd  v[800005];
int t1[400005];
short int h[400005];
int findset(int x)
{
    while(t1[x]!=x)x=t1[x];
    return x;
}
void unionset(int x,int y)
{
    if(h[x]<h[y])t1[x]=y;
    if(h[x]>h[y])t1[y]=x;
    if(h[x]==h[y])
        h[x]++,t1[y]=x;
}
int st[1000005],cnt=0;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n , m ,x , y,s,i,z;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        t.x=x;t.y=y;
        t.z=z;
        v[i]=t;
    int aux=t.x;
    t.x=t.y;
    t.y=aux;
    v[m+i]=t;
    }
    sort(v+1,v+2*m+1,cmp);
    for(i=1;i<=n;i++)t1[i]=i,h[i]=1;
    int sum=0;
    for(i=1;i<=2*m;i++)
    {
        int l1=findset(v[i].x),l2=findset(v[i].y);
        if(l1!=l2)
        {
            if(cnt==n-1)break;
            unionset(l1,l2);
            sum+=v[i].z;
            st[++cnt]=i;
        }
    }
    printf("%d\n",sum);
    printf("%d\n",n-1);
    for(i=1;i<=n-1;i++)
        printf("%d %d\n",v[st[i]].x,v[st[i]].y);
return 0;
}