#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,em;
struct vec
{
    int x;
    int y;
    int c;
}v[400003];
int m[400003];
struct solutie
{
    int a;
    int b;
}sol[400003];
bool compare(struct vec a,struct vec b)
{
    return a.c<b.c;
}
int main()
{
    f>>n>>em;
    for(int i=1;i<=em;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+em+1,compare);
    //punem elementele in multimi diferite
    for(int i=1;i<=n;i++)
        m[i]=i;
    int nr=0;
    int it=1;
    int val;
    int val2;
    int cost=0;
    while(nr<n-1&&nr<em)
    {
        if(m[v[it].x]!=m[v[it].y])
        {
            nr++;
            sol[nr].a=v[it].x;
            sol[nr].b=v[it].y;
            cost+=v[it].c;
            val=m[v[it].y];
            for(int i=1;i<=n;i++)
            {
                if(m[i]==val)
                    m[i]=m[v[it].x];
            }
        }
        it++;
    }
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=1;i<=n-1;i++)
    {
        g<<sol[i].a<<" "<<sol[i].b<<"\n";
    }
    return 0;
}