#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,CostAPM;
struct Muchie
{
    int e1;
    int e2;
    int cost;
};
int A[100],c[100];
Muchie graf[100];

void Initializare()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
            f>>graf[i].e1>>graf[i].e2>>graf[i].cost;
    for(int i=1;i<=n;++i)
        c[i] = i;
    f.close();
}

void SortareMuchii(int l, int r)
{
    Muchie x;
    if(l<r)
    {
        x = graf[l];
        int i=l;
        int j=r;
        while(i<j)
        {
            while(i<j && graf[j].cost >= x.cost) --j;
            graf[i] = graf[j];
            while(i<j && graf[i].cost <= x.cost) ++i;
            graf[j] = graf[i];
        }
        graf[i] = x;
        SortareMuchii(l,i-1);
        SortareMuchii(i+1,r);
    }
}

void Afisare()
{
    for(int i=1;i<n;++i)
    {
        g<<graf[A[i]].e1<<" "<<graf[A[i]].e2<<'\n';
        CostAPM += graf[A[i]].cost;
    }
}

int main()
{
    Initializare();
    SortareMuchii(1,m);
    int NrMuchii = 0;
    for(int i=1;NrMuchii<n-1;++i)
        if(c[graf[i].e1] != c[graf[i].e2])
        {
            A[++NrMuchii] = i;

            int maxim = max(c[graf[i].e1],c[graf[i].e2]);
            int minim = min(c[graf[i].e1],c[graf[i].e2]);
            CostAPM += graf[i].cost;


            for(int j=1;j<=n;++j)
                if(c[j] == maxim) c[j] = minim;
        }
    g<<CostAPM<<'\n'<<NrMuchii<<'\n';
    Afisare();
    return 0;
}