#include <fstream>
#include <algorithm>
#include <vector>
 
#define max 400100
using namespace std;
 
ifstream cin("apm.in");
ofstream cout("apm.out");
int n, m, x[max], y[max], cost[max], indice[max], gr[max], rez;
vector <int> apm;
inline bool cmp ( int a, int b )
{
    return (cost[a] < cost[b]) ;
}
int padure(int i)
{
    if(gr[i] == i) return i;
    gr[i] = padure(gr[i]);
    return gr[i];
}
void reuneste (int i, int j)
{
    gr[padure(i)] = padure(j);
}
int main()
{
    cin >> n >> m;
    for( int i = 1 ; i <= m ; ++ i )
    {
        cin>> x[i] >> y[i] >> cost[i];
        indice[i] = i ;
    }
 
    sort( indice + 1, indice + m + 1, cmp );
 
    for(int  j = 1;  j <= n ; ++ j)
        gr[j] = j ;
 
    for ( int i = 1 ; i <= m ; ++ i )
    {
        if(padure(x[indice[i]]) != padure(y[indice[i]]))
        {
            rez += cost[indice[i]];
            reuneste ( x[indice[i]], y[indice[i]] ) ;
            apm.push_back(indice[i]);
        }
    }
 
    cout<<rez<<"\n"<<n-1<<"\n";
    for( int i = 0 ; i < n-1 ; ++ i)
        cout<<x[apm[i]]<<" "<<y[apm[i]]<<"\n";
 
    cin.close();
    cout.close();
    return 0;
}