#include <fstream>
#include <algorithm>


using namespace std;

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

int i,n,m,t[400010],C[400010],A[400010],k;

struct muchie{

    int x;
    int y;
    int cost;


}v[400010];

int cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int query(int x, int y){

    int a = x;
    int b = y;

    while(t[x] > 0)
        x = t[x];

    while(t[y] > 0)
        y = t[y];

    if(x == y)
        return 0;

    A[++k] = a;
    A[++k] = b;
    return 1;

}

void update(int x, int y, int poz){

    //int a = x;
    //int b = y;

    while(t[x] > 0)
        x = t[x];

    while(t[y] > 0)
        y = t[y];

    if(t[x] <= t[y])
    {
        t[x] += t[y];
        t[y] = x;

        if(C[x] == 0)
        {
            C[x]+=v[poz].cost;
        }
        else
            {
                if(C[y] == 0)
                {
                    C[x] += v[poz].cost;
                }
                else
                    C[x]+= C[y] + v[poz].cost;
            }
    }
    else
    {
        t[y] += t[x];
        t[x] = y;
        if(C[y] == 0)
        {
            C[y] += v[poz].cost;
        }
        else
            if(C[x] == 0)
            {
                C[y] += v[poz].cost;
            }
            else
            {
                C[y] += C[x] + v[poz].cost;
            }
    }

}

int main()
{

    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }

    sort(v + 1, v + m + 1, cmp);

    for(int i = 1; i <= n; i ++)
    {
        t[i] = -1;
    }

    for(int i = 1; i <= m; i ++)
    {
        if(query(v[i].x, v[i].y))
        {
            update(v[i].x, v[i].y,i);
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        if(t[i] < 0)
        {
            fout << C[i] << '\n' << -(t[i] + 1) << '\n';
            break;
        }
    }
    for(int i = 1; i <= k; i++)
    {
        fout << A[i] << " ";
        if(i % 2 == 0)
        {
            fout << '\n';
        }
    }

    return 0;
}