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

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

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

int n , m , t[200002];
 queue<pair<int,int>>Q;
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]){
           
            Q.push({x[i].i,x[i].j});
            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';
    while(!Q.empty()){
        cout<<Q.front().first<<" "<<Q.front().second<<'\n';
        Q.pop();
    }
    return 0;
}