#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,conex[200001],cnt,costmin;
struct muchie
{
    int x,y,c;
}sol[200001],v[400001];

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

int test(muchie a,muchie b)
{
    return a.c<b.c;
}

void kruskal()
{
    sort(v+1,v+m+1, test);
    int k=1;
    while(cnt<n-1)
    {
        if(conex[v[k].x]!=conex[v[k].y])
        {
            sol[++cnt]=v[k];
            costmin+=v[k].c;
            int a=conex[v[k].x], b=conex[v[k].y];
            for(int i=1; i<=n; ++i)
                if(conex[i]== a)
                conex[i]= b;
        }
        ++k;
    }
}
int main()
{
    citire();
    kruskal();
    g<<costmin<<'\n'<<n-1<<'\n';
    for(int i=1; i<=n-1; ++i)
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
    g.close();
    return 0;
}