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

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

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

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

    fin.close();
}

void apm(){
    key.at(1) = 0;
    pQueue.push(1);

    while(!pQueue.empty()){

        int currentNode = pQueue.top();
        pQueue.pop();
        wasInQueue.at(currentNode) = true;
        inTree.at(currentNode) = true;

        for(auto& elem:graph.at(currentNode)){

            if(!inTree.at(elem.first)){

                if(elem.second < key.at(elem.first)){

                    key.at(elem.first) = elem.second;
                    parent.at(elem.first) = currentNode;

                    if(!wasInQueue.at(elem.first)) pQueue.push(elem.first);
                }
            }
        }
    }
}

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

    int cost = 0;
    int nr = 0;

    for(int i=1; i<=n; i++){
        for(auto& elem:graph.at(i)) if(elem.first==parent.at(i)){
            cost += elem.second;
            nr++;
        }
    }
    ofstream fout("apm.out");
    fout<<cost<<endl<<nr<<endl;

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