#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct Edge{
    int nod1, nod2, cost;
};

Edge v[400005],ans[400005];

bool order(Edge a, Edge b){
    if(a.cost < b.cost)  // ordonam muchiile dupa cost
        return true;
    if(a.cost == b.cost && a.nod1 < b.nod1)  // si apoi dupa primul nod
        return true;
    return false;
}

int parent[200005];

int absolute_parent(int x)  // functia care intoarce valoarea parintelui absolut (radacinii)
{
    if(parent[x] == x)
        return x;
    return parent[x] = absolute_parent(parent[x]);  // o apelam recursiv pana la radacina
}

void unite(int x, int y)
{
    parent[absolute_parent(x)] = absolute_parent(y);  // uneste cele doua ramuri atribuind acelasi parinte nodului 2
}

int main()
{
    int n, m, res=0, cost=0, i;
    in >> n >> m;

    for(i = 1; i <= m; ++i)
        in >> v[i].nod1 >> v[i].nod2 >> v[i].cost;  // citim pe rand din fisier muchiile si costul

    for(i = 1; i <= n; ++i)
        parent[i] = i;  // fiecare nod este initial parintele propriu

    sort(v+1, v+m+1, order);  // sortam muchiile

    for(i = 1; i <= m && res < n-1; ++i)
        if(absolute_parent(v[i].nod1) != absolute_parent(v[i].nod2)){  // daca doua noduri nu au acelasi parinte absolut, adaugam muchia dintre ele la APM
            ++res;
            ans[res] = v[i];
            cost += v[i].cost;
            unite(absolute_parent(v[i].nod1), absolute_parent(v[i].nod2));
        }
    out<<cost<<'\n'<<n-1<<'\n';

    for(i=1;i<=n-1;++i)
        out<<ans[i].nod2<<" "<<ans[i].nod1<<'\n';
    return 0;
}