#include <bits/stdc++.h>

using namespace std;
#define NMAX 200001
#define oo 1000000000
int n, m;
vector<vector<pair<int,int>>> graph(NMAX);

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.at(x).push_back(make_pair(y,c));
        graph.at(y).push_back(make_pair(x,c));
    }
    fin.close();
}

vector<int> parent(NMAX);
vector<int> key(NMAX, oo);

struct comp{
    bool operator()(const int& a, const int& b) const{
        return key.at(a) > key.at(b);
    }
};
priority_queue<int, vector<int>, comp> Queue;

int cost=0, nr=-1;
vector<bool> inTree(NMAX);

void apm(){
    key.at(1) = 0;
    for(int i=1; i<=n; i++) Queue.push(i);

    int currendNode;

    while(!Queue.empty()){

        currendNode = Queue.top();


        inTree.at(currendNode)=true;

        nr++;

        for(auto& elem:graph.at(currendNode)){
                if(!inTree.at(elem.first))
            if(elem.second < key.at(elem.first)){
                parent.at(elem.first) = currendNode;
                key.at(elem.first) = elem.second;
            }
        }
        Queue.pop();
    }
}

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

    ofstream fout("apm.out");

    for(int i=2; i<=n; i++){
        for(auto& elem:graph.at(parent.at(i))) if(elem.first == i){cost+= elem.second; break;}
    }
    fout<<cost<<endl;
    fout<<nr<<endl;

    for(int i=2; i<=n; i++){
        fout<<parent.at(i)<<" "<<i<<endl;
    }
}