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

using namespace std ;

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

const int MAXN = 400000 ;

int n, m, min_cost, idx[MAXN + 10], group[MAXN + 10], x[MAXN + 10], y[MAXN + 10], cost[MAXN + 10] ;
vector < int > ans ;

int get_group (int x)
{

    if (group[x] == x)
        return x ;

    group[x] = get_group (group[x]);
    return group[x] ;

}

void reunion (int x, int y)
{

    group[get_group(x)] = get_group(y) ;

}

bool cmp (int x, int y)
{

    return (cost[x] < cost[y]) ;

}


int main()
{

    cin >> n >> m ;

    for (int i = 1 ; i <= m ; i ++)
        cin >> x[i] >> y[i] >> cost[i], idx[i] = i ;

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

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

    for (int i = 1 ; i <= m ; i ++)
    {

        if (get_group(x[idx[i]]) != get_group(y[idx[i]]))
        {

            min_cost += cost[idx[i]] ;
            reunion(x[idx[i]], y[idx[i]]) ;
            ans.push_back (idx[i]) ;

        }

    }

    cout << min_cost << '\n' << ans.size() << '\n' ;

    for (auto item : ans)
        cout << x[item] << ' ' << y[item] << '\n' ;


    return 0 ;

}