#include<bits/stdc++.h>
#define Nmax 200010
#define Mmax 400010
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct lista
{int x,y,c;};
lista M[Mmax];
bool cmp(lista a,lista b)
{return a.c<b.c;
}
struct muchie
{int x,y;};
muchie apm[Nmax];
int n,m,tata[Nmax],h[Nmax],s,nr;
void Union(int x,int y)
{
    if(h[x]>h[y])
        tata[y]=x;
    else
        tata[x]=y;
    if(h[x]==h[y])
        h[x]++;
}
int Find(int R)
{
    while(tata[R]!=R)
        R=tata[R];
    return R;
}
void Kruskal()
{int R1,R2;
    for(int i=1; i<=n; i++)
    {
        tata[i]=i;
        h[i]=1;
    }
    sort(M+1,M+m+1,cmp);

    for(int i=1; i<=m,nr<n-1; i++)
    { R1=Find(M[i].x);
      R2=Find(M[i].y);
        if(R1!=R2)
        {   Union(R1,R2);
            s+=M[i].c;
            apm[++nr].x=M[i].x;
            apm[nr].y=M[i].y;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>M[i].x>>M[i].y>>M[i].c;
     Kruskal();
    g<<s<<'\n'<<n-1<<'\n';
    for(int i=1;i<=nr;i++)
      g<<apm[i].x<<' '<<apm[i].y<<'\n';
    return 0;
}