#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n, m, cost_apm;
struct { int x, y, c; } M[400010];
vector < int > V[200010], Sol;
multiset < pair < int, int > > Heap;
bool fr[200010];
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> M[i].x >> M[i].y >> M[i].c;
        V[M[i].x].push_back(i);
        V[M[i].y].push_back(i);
    }
    fr[1] = true;
    for (int i = 0; i < V[1].size(); i++) Heap.insert( { M[V[1][i]].c, V[1][i] } );
    for (int i = 1; i < n; i++)
    {
        while (true)
        {
            if (fr[M[Heap.begin()->second].x] && fr[M[Heap.begin()->second].y]) Heap.erase(Heap.begin());
            else break;
        }
        int nod;
        if (fr[M[Heap.begin()->second].y]) nod = M[Heap.begin()->second].x;
        else nod = M[Heap.begin()->second].y;
        Sol.push_back(Heap.begin()->second);
        fr[nod] = true;
        cost_apm += Heap.begin()->first;
        Heap.erase(Heap.begin());
        for (vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); it++) Heap.insert( { M[*it].c, *it } );
    }
    fout << cost_apm << '\n' << n - 1 << '\n';
    for (auto it : Sol) fout << M[it].x << ' ' << M[it].y << '\n';
    return 0;
}