#include <fstream>
#include <cstdlib>
using namespace std;
int n,m,i,j,k,GR[40001],s,a,b,c,w[40001];
struct muchie
{
    int x,y,c;
} v[400001];
int cmp(const void*a, const void*b)
{
    muchie c,d;
    c=*(muchie*)a;
    d=*(muchie*)b;
    return (c.c-d.c);
}
int grupa(int a)
{
    if(GR[a]==a) return a;
    else return GR[a]=grupa(GR[a]);
}
void reuniune(int i,int j)
{
    GR[grupa(i)]=grupa(j);
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    for(i=1;i<=n;i++) GR[i]=i;
    qsort(v,m,sizeof(muchie),cmp);
    j=0;k=0;s=0;
    while(j<m&&k<n-1)
    {
     a=v[j].x;
     b=v[j].y;
     c=v[j].c;
     if(GR[a]!=GR[b])
     {
         k++;
         w[k]=j;
         s=s+c;
         reuniune(a,b);
     }
     j++;
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for(i=1;i<=k;i++)
    fout<<v[w[i]].y<<' '<<v[w[i]].x<<'\n';
    fout.close();
    return 0;
}