#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, c, nr=0, costulMinim = 0;

struct myArbore
{
    int a, b, cost;
    bool v;

} arb[200001];

int t[200001];

void sortam()
{
    bool sortat;
    do
    {
        sortat = true;
        for(int i = 1 ; i<m ; i ++)
            if(arb[i].cost > arb[i+1].cost)
            {
                swap(arb[i].a, arb[i+1].a);
                swap(arb[i].b, arb[i+1].b);
                swap(arb[i].cost, arb[i+1].cost);
                sortat = false;
            }
    }
    while(!sortat);

//    for(int i=0; i<m; i++)
//        cout<<arb[i].b<<" "<<arb[i].a<<" "<<arb[i].cost<<endl;
}

int main()
{
    fin>>n>>m;

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


    sortam();

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

    for(int i=1; i<=m && nr < n; i++)
    {
        //cout<<arb[i].b<<" "<<arb[i].a<<" "<<arb[i].cost<<" vine acum : ";
        if(t[arb[i].a] != t[arb[i].b])
        {
            nr++;
            costulMinim += arb[i].cost;
            //cout<<arb[i].b<<" "<<arb[i].a<<" "<<arb[i].cost<<" vine acum: ";
            arb[i].v = true ;
           // cout<<v[i].f<<" "<<v[i].s<<endl;

            int ai = t[arb[i].a];
            int bi = t[arb[i].b];

            for(int j=1; j<=n; j++)
                if(t[j] == bi)
                    t[j] = ai;
        }
    }

    fout<<costulMinim<<endl<<nr<<endl;

    for(int i=1; i<=m; i++)
       if(arb[i].v == true)
            fout<<arb[i].b<<" "<<arb[i].a<<endl;

    return 0;
}