#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];
vector <muchie> apm;
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;
 muchie aux;
    for(int i=1; i<=n; i++)
    tata[i]=i;

    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;
            aux.x=M[i].x;
            aux.y=M[i].y;
            apm.push_back(aux);
        }
    }
}
int main()
{vector <muchie> :: iterator it;
    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';*/
   for(it=apm.begin();it!=apm.end();++it)
     g<<it->x<<' '<<it->y<<'\n';
      f.close(); g.close();
    return 0;
}