#include <bits/stdc++.h>
#define NMAX 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int tata[NMAX],RG[NMAX],i,n,m,k,s,tatal_x,tatal_y;
struct
{
    int first,second;
}p[NMAX];
struct muchie
{
    int x,y,c;
}v[NMAX];
bool cmp(muchie i, muchie j)
{
    return i.c<j.c;
}
int Find(int nod)
{
    while(tata[nod]!=nod) nod=tata[nod];
    return nod;
}
void unire(int x, int y)
{
    if(RG[x] < RG[y]) tata[x] = y;
    if(RG[x] > RG[y]) tata[y] = x;
    if(RG[x] == RG[y])
    {
        tata[x] = y;
        RG[y]++;
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
        fin>>v[i].x>>v[i].y>>v[i].c;
    for(i=1;i<=n;++i)
    {
        RG[i]=1;
        tata[i]=i;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;++i)
    {
        tatal_x=Find(v[i].x);
        tatal_y=Find(v[i].y);
        if(tatal_x!=tatal_y)
        {
            unire(tatal_x, tatal_y);
            p[++k].first=v[i].x;
            p[k].second=v[i].y;
            s+=v[i].c;
        }
    }
    fout<<s<<"\n"<<n-1<<"\n";
    for(i=1;i<=k;++i)
        fout<<p[i].first<<" "<<p[i].second<<"\n";
    return 0;
}