/// PRIM N^2
#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cassert>
using namespace std;

ifstream in("apm.in");
//ofstream out("apm.out");

const int INF = 1001;
const int N = 200001;
const bool DEBUG = false;

struct node{
    int index;
    int cost_to_reach = INF;
    int parent_to_reach = -2;
    bool is_in_the_tree = false;
};

vector<pair<int, int> > neighbours[N]; /// index_neighbour, cost
node v[N];
int n,m;

void expandTree(){
    /// Find the best node to be added into the tree
    int best_new_index = -1;
    int best_cost = INF;;
    for(int i=1; i<=n; ++i)
        if(!v[i].is_in_the_tree && v[i].cost_to_reach < best_cost){
            best_cost = v[i].cost_to_reach;
            best_new_index = i;
        }

    /// If we cannot join a new node, we shouldn't call this function :)
    assert(best_new_index != -1);

    /// Add it into the tree
    v[best_new_index].is_in_the_tree = true;

    /// Check its neighbours and Update their cost_to_reach
    for(auto &neighbour : neighbours[best_new_index])
        if(!v[neighbour.first].is_in_the_tree && neighbour.second < v[neighbour.first].cost_to_reach){
            v[neighbour.first].cost_to_reach = neighbour.second;
            v[neighbour.first].parent_to_reach = best_new_index;
        }
}

int main()
{
    /// Input
    freopen("apm.out","w",stdout);

    in>>n>>m;
    for(int i=0; i<m; ++i){
        int index_1, index_2, cost;
        in>>index_1>>index_2>>cost;

        neighbours[index_1].push_back({index_2, cost});
        neighbours[index_2].push_back({index_1, cost});
    }

    /// Init
    for(int i=1; i<=n; ++i){
        v[i].index = i;
    }

    /// Solve
    v[1].cost_to_reach = 0;
    for(int i=1; i<=n; ++i){
        expandTree();

        if(DEBUG){
            cout<<"-------------------------------\n";
            for(int j=1; j<=n; ++j)
                if(v[j].is_in_the_tree)
                    cout<<"Node "<<j<<" is in the tree!\n";
        }
    }

    /// Print Solution
    int tree_cost = 0;
    for(int i=1; i<=n; ++i)
        tree_cost += v[i].cost_to_reach;
    //cout<<"Tree cost = ";
    cout<<tree_cost<<"\n";
    cout<<n-1<<"\n";
    for(int i=1; i<=n; ++i)
        if(v[i].parent_to_reach != -2)
            cout<<v[i].parent_to_reach<<" "<<i<<"\n";


    /// Test
    if(DEBUG){
        for(int i=1; i<=n; ++i){
            for(auto &neighbour : neighbours[i])
                cout<<i<<" "<<neighbour.first<<" "<<neighbour.second<<"\n";
        }
    }

    return 0;
}