#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int Max = 200007;

struct edge
{
    int x, y, c;
    bool operator <(const edge &aux)const
    {
        return c < aux.c;
    }
}muc[Max * 2];
vector<int> sol;
int rad[Max], h[Max];

int kok(int x)
{
    int y = x;
    for(;x!=rad[x];x=rad[x]);
    while(y != x)
    {
        int aux = rad[y];
        rad[y] = x;
        y = aux;
    }
    return x;
}

int main()
{
    int n, m, t = 0;
    in >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        in >> muc[i].x >> muc[i].y >> muc[i].c;
    }
    sort(muc + 1, muc + 1 + m);

    for(int i = 1; i <= n; ++i)
    {
        rad[i] = i;
        h[i] = 1;
    }
    for(int i = 1; i <= m; ++i)
    {
        int x = kok(muc[i].x), y = kok(muc[i].y);
        if(x != y)
        {
            if(h[x] < h[y])
            {
                swap(x, y);
            }
            rad[y] = x;
            if(h[x] == h[y])
                h[x]++;
            sol.push_back(i);
            t+= muc[i].c;
        }
    }
    out << t << "\n" << sol.size() << "\n";
    for(int i = 0; i < sol.size(); ++i)
    {
        out << muc[sol[i]].x << " " << muc[sol[i]].y << "\n";
    }
}