#include <bits/stdc++.h>
#define NMAX 200005
#define MMAX 400005

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

int n, m, X, Y, sol[NMAX], k;
long long s ;
struct MakePer
{
    int x, y, c ;
};
MakePer v[MMAX], a[NMAX];

bool acompare(MakePer lhs , MakePer rhs)
{
    return lhs.c < rhs.c ;
}

int FindRoute(int x)
{
    int y = x, z ;
    while(sol[x] != 0)
        x = sol[x] ;
    while(y != x)
    {
        z = sol[y] ;
        sol[y] = x ;
        y = z ;
    }
    return x ;
}

int main()
{
    fin >> n >> m ;
    for(int i=1; i<=m; i++)
        fin >> v[i].x >> v[i].y >> v[i].c ;
    std::sort(v+1 , v+m+1, acompare) ;
    for(int i=1; i<=m; i++)
    {
        X = FindRoute(v[i].x) ;
        Y = FindRoute(v[i].y) ;
        if(X != Y)
        {
            k ++ ;
            sol[X] = Y ;
            a[k].x = v[i].x ;
            a[k].y = v[i].y ;
            s = s + v[i].c ;
        }
        if(k == n-1)
            break ;
    }
    fout << s << "\n" << k << "\n" ;
    for(int i=1; i<=k; i++)
        fout << a[i].x << " " << a[i].y << "\n" ;

    return 0;
}