#include <bits/stdc++.h>

using namespace std;

#define infinity 1<<30

vector<vector<pair<int, int> > > graph;

int m, n;

vector<int> key;

struct comp{

    bool operator()(int x, int y){

        return key.at(x) > key.at(y);

    }
};

priority_queue<int, vector<int>, comp> q;

vector<bool> inAPM;

vector<int> parent;

vector<bool> inQueue;

void apm(){

    key.resize(n+1, infinity);

    inAPM.resize(n+1, false);

    inQueue.resize(n+1, false);

    parent.resize(n+1, -1);

    key.at(1) = 0;

    q.push(1);

    while(!q.empty()){

        int node = q.top();

        q.pop();

        inQueue.at(node) = false;

        inAPM.at(node) = true;

        for(auto& neighbour:graph.at(node)){

            if(inAPM.at(neighbour.first)==false){

                if(key.at(neighbour.first)>neighbour.second){

                    key.at(neighbour.first) = neighbour.second;

                    if(inQueue.at(neighbour.first)==false)
                    {
                        q.push(neighbour.first);

                        inQueue.at(neighbour.first) = true;
                    }


                    parent.at(neighbour.first) = node;
                }
            }
        }
    }


}

int main()
{
    ifstream fin("apm.in");

    ofstream fout("apm.out");

    fin>>n>>m;

    graph.resize(n+1, vector<pair<int, int> >());

    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));
    }

    apm();

    int cost=0;

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

        cost+=key.at(i);

    }

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

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

        fout<<parent.at(i)<<" "<<i<<endl;

    }
}