#include<stdio.h>
#include<string.h>
#include<algorithm>
#define Nmax 200001
#define Mmax 400001

int n,m,nr,S[Nmax],t[Nmax];
struct much
{
    int x,y,c;
};

much a[Mmax];

using namespace std;

void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
}

bool cmp(much g,much h)
{
    return g.c<h.c;
}

int rd(int x)
{
    int M=x,y;
    while(t[M]!=M)
       M=t[M];
    while(t[x]!=M)
    {
        y=t[x];
        t[x]=M;
        x=y;
    }

}

void unesc(int i,int j)
{
    t[rd(i)]=rd(j);
}

void solve()
{
    int sol=0;
    for(int i=1;i<=n;++i) t[i]=i;
    for(int i=1;i<=m&&nr<n;++i)
      {
         if(rd(a[i].x)!=rd(a[i].y))
         {
            sol+=a[i].c;
            unesc(rd(a[i].x),rd(a[i].y));
            S[++nr]=i;
         }
      }
    printf("%d\n%d\n",sol,n-1);
    for(int i=1;i<n;++i)
      printf("%d %d\n",a[S[i]].x,a[S[i]].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(a+1,a+m+1,cmp);
    solve();
    return 0;
}