#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int maxv = 400005;

struct edge
{
    int x, y, c;
};
edge v[maxv];

int arbore[maxv], ind[maxv], rez;
vector<int> muchii_arbore;

int caut(int i)
{
	if (arbore[i] == i) return i;
	arbore[i] = caut(arbore[i]);
	return arbore[i];
}

void reuniune(int i,int j)
{
	arbore[caut(i)] = caut(j);
}


int main()
{
    int n, m, x, y, c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].c;
        ind[i] = i;
    }

    for(int i = 1; i <= n; i++)
        arbore[i] = i;

    sort(ind+1, ind+m+1, [&](int a, int b){if(v[a].c < v[b].c) return true; return false;});

    for(int i = 1; i <= m; i++)
    {
        if(caut(v[ind[i]].x) != caut(v[ind[i]].y))
        {
            rez += v[ind[i]].c;
            reuniune(v[ind[i]].x, v[ind[i]].y);
            muchii_arbore.push_back(ind[i]);
        }
    }

    fout << rez << "\n";
    fout << n-1 << "\n";
    for(auto k : muchii_arbore)
        fout << v[k].x << " " << v[k].y << "\n";
    return 0;
}