#include <bits/stdc++.h>
#define infinity 1000000000
#define NMAX 200001
using namespace std;

vector<vector<pair<int,int>>> graph(NMAX);
int n, m;

void readFromFile(){
    ifstream fin("apm.in");
    fin>>n>>m;
    int x, y, c;
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph[x].push_back(make_pair(y, c));
        graph[y].push_back(make_pair(x, c));
    }
    fin.close();
}


vector<int> parent(NMAX);
vector<int> key(NMAX, infinity);
vector<bool> inTree(NMAX, false);

void getMinKeyIndex(int &node){
    int _min = infinity;
    for(int i=1; i<=n; i++)
    if(inTree[i]==false && _min>key[i]){
        _min = key[i];
        node = i;
    }
}


int cost = 0;
void apm(){
    key[1] = 0;
    int node;

    for(int i=1; i<=n; i++){

        getMinKeyIndex(node);
        inTree[node] = true;
        cost += key[node];

        for(auto& elem:graph[node]){
            if(!inTree[elem.first] && (elem.second < key[elem.first])){
                parent[elem.first] = node;
                key[elem.first] = elem.second;
            }
        }
    }
}


int main()
{
    readFromFile();
    apm();

    ofstream fout("apm.out");

    fout<<cost<<endl<<n-1<<endl;

    for(int i=2; i<=n; i++) fout<<i<<" "<<parent[i]<<endl;

    fout.close();
}