#include <bits/stdc++.h>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct Muchie
{
    int x, y, cost;
    bool check;
}muc [400001];
int t[200001], n, m;

bool CMP(Muchie A, Muchie B)
{
    return A.cost < B.cost;
}

void Union(int x, int y)
{
    t[x] = y;
}
int Find(int x)
{
    int rad = x, y;
    while(t[rad] != 0)
        rad = t[rad];
    while(x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}

void Read()
{
    int x, y, cost;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        muc[i].x = x;
        muc[i].y = y;
        muc[i].cost = cost;
    }
}
queue<int> q;
void Kruskal()
{
    int nrcc = n, costMin = 0, x, y;
    sort(muc + 1, muc + m + 1, CMP);
    for(int i = 1; i <= m && nrcc > 1; i++)
    {
        x = Find(muc[i].x);
        y = Find(muc[i].y);
        if(x != y)
        {
            nrcc--;
            costMin += muc[i].cost;
            muc[i].check = true;
            Union(x, y);
        }
    }
    fout << costMin << "\n";
    for(int i = 1; i<= m; i++)
        if(muc[i].check == true)
            q.push(i);
    fout << q.size() << "\n";
    while(q.empty() == false)
    {
        fout << muc[q.front()].x << " " << muc[q.front()].y <<  "\n";
        q.pop();
    }

}
int main()
{
    Read();
    Kruskal();
    return 0;
}