// #include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

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

struct muchie{
    int i,j,cost;
};

int n , m , t[200002];

muchie x[400002];
int v[400002];

bool comp(muchie a,muchie b){
    return a.cost<b.cost;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 0 ; i < m ; ++i)
        cin >> x[i].i >> x[i].j >> x[i].cost;

    sort(x,x+m,comp);

    for(int i =1 ; i <= n ; ++i)
        t[i] = i;
    int s = 0, cnt = 0;
    
    for(int i=0;i<m && cnt<n;++i)
        if(t[x[i].i]!=t[x[i].j]){
            v[i]=1;
            s+=x[i].cost;
            int ti=t[x[i].i],tj=t[x[i].j];
            
            for(int j=1;j<=n;++j)
                if(t[j]==tj)
                    t[j]=ti;
        }
    cout<<s<<'\n'<<n-1<<'\n';
    for(int i=0;i<m;++i)
        if(v[i])
            cout<<x[i].i<<" "<<x[i].j<<'\n';
    return 0;
}