#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,cost,c[400001];

vector<bool>sol;

struct muchii
{
    int x,y,z;
}v[400001];

bool cmp(muchii p,muchii q)
{
    return p.z < q.z;
}



void citire()
{
    int i;
    f>>n>>m;
    sol=vector<bool>(m+1);
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].z;
    }
}

void kruskal()
{
    int i, sel=0;
    for(i=1;i<=n;i++) c[i]=i;
    i=1;
    while(sel!=n-1)
    {
            if(c[v[i].x]!=c[v[i].y])
        {
            cost+=v[i].z;
            sel++;
            sol[i]=1;
          int   mx=max(c[v[i].x],c[v[i].y]);
          int  mn=min(c[v[i].x],c[v[i].y]);
            for(int j=1;j<=n;j++)
            if(c[j]==mx) c[j]=mn;

        }
        i++;
    }

}

void afisare()
{
    int i;
    g<<cost<<"\n"<<n-1<<"\n";
    for(i=1;i<=m;i++)
        if(sol[i]==1) g<<v[i].x<<" "<<v[i].y<<"\n";
}


int main()
{
    citire();
    sort(v+1,v+m+1,cmp);
    kruskal();
    afisare();
    return 0;
}