#include<fstream>
#include<iostream>
#include<vector>
#define maxn 200005
#define maxm 400005

using namespace std;

vector< pair<int,int> > v[maxn];
pair<int,int> dist[maxn], rez[maxn];
int taken[maxn];

int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m, i, j, x, y, cost, k, min, nod;
    f>>n>>m;
    for (i = 1; i <= m; i++){
        f>>x>>y>>cost;
        v[x].push_back(make_pair(y, cost));
        v[y].push_back(make_pair(x, cost));
    }
    
    for (i = 1; i <= n; i++)
        dist[i] = make_pair(0, 1000000000);
    
    taken[1] = 1;
    for (i = 0; i < v[1].size(); i++)
        dist[v[1][i].first] = make_pair(1, v[1][i].second);     
    
    long long c = 0;
    for (i = 1; i <= n-1; i++){
        min = 1000000001;
        for (j = 1; j <= n; j++){
            if (taken[j] == 0 && dist[j].second < min){
                min = dist[j].second;
                nod = j;    
            }    
        }
        taken[nod] = 1;
        rez[i] = make_pair(nod, dist[nod].first);
        c = c+min;
        for (j = 0; j < v[nod].size(); j++){
            if (taken[v[nod][j].first] == 0 && dist[v[nod][j].first].second > v[nod][j].second)
                dist[v[nod][j].first] = make_pair(nod, v[nod][j].second);       
        }   
    }
    
    g<<c<<'\n'<<n-1<<'\n';
    for (i = 1; i <= n-1; i++){
        g<<rez[i].first<<" "<<rez[i].second<<'\n';      
    }
    
    return 0;
}