#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ofstream fout("apm.out");
ifstream fin("apm.in");
const int NMAX = 400005;

int n, m, cost, nr;
int Set[NMAX];

struct muchie { int x, y, c; };
vector<muchie> Arbore;
vector<muchie> v;

bool cmp(muchie a, muchie b) { return a.c < b.c; }

void citire()
{
    int x, y, c;

    fin >> n >> m;
    for(int i=0; i<m; i++) {
        fin >> x >> y >> c;
        v.push_back({x,y,c});
        Set[i] = i;
    }
}

int find_set(int a)
{
    while(Set[a] != a) a = Set[a];
    return a;
}

void unite_set(int a, int b)
{
    int aux1, aux2;

    aux1 = find_set(a);
    aux2 = find_set(b);
    Set[aux1] = aux2;
}

void afis()
{
    fout << cost << '\n' << Arbore.size() << '\n';
    for(int i=0; i<Arbore.size(); i++) fout << Arbore[i].y << ' ' << Arbore[i].x << '\n';
}

int main()
{
    citire();
    sort(v.begin(), v.end(), cmp);

    for(int i=0; i<v.size(); i++) {
        if( find_set(v[i].x) != find_set(v[i].y) )
        {
            unite_set(v[i].x, v[i].y);
            Arbore.push_back({v[i].x, v[i].y, v[i].c});
            cost += v[i].c;
        }
    }
    afis();
    return 0;
}