#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 200005
#define MAXM 400005

using namespace std;

int n, m;

struct muchie
{
    int a, b, cost;
};
vector<muchie> muchii;
vector<pair<int,int> >apm;
int cost_apm;

struct comparator
{
    bool operator()(muchie x, muchie y)
    {
        return x.cost < y.cost;
    }
};

int tata[MAXN];


void citire()
{
    scanf("%d %d ",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int a, b, c;
        scanf("%d %d %d ",&a,&b,&c);
        muchii.push_back({a,b,c});
        muchii.push_back({b,a,c});
    }
}

int get_tata(int nod)
{
    int result;
    for(result = nod;result != tata[result]; result = tata[result]);
    return result;
}

void kruskal()
{
    for(int i=1;i<=n;i++)
        tata[i] = i;

    sort(muchii.begin(),muchii.end(),comparator());

    for(int i=0;i<muchii.size();i++)
    {
        int tata_a = get_tata(muchii[i].a), tata_b = get_tata(muchii[i].b);

        if(tata_a != tata_b)
        {
            apm.push_back(make_pair(muchii[i].a,muchii[i].b));
            tata[tata_a]=tata_b;
            cost_apm += muchii[i].cost;
        }
    }
}

void afisare()
{
    printf("%d\n%d\n",cost_apm,apm.size());
    for(int i=0;i<apm.size();i++)
        printf("%d %d\n",apm[i].first,apm[i].second);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    kruskal();
    afisare();
    return 0;
}