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

ifstream fin("apm.in");
ofstream fout("apm.out");

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

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pQueue;

vector<bool> inApm = vector<bool>(NMAX, false);
vector<int> key = vector<int>(NMAX, INT_MAX);
vector<int> parent = vector<int>(NMAX);

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

    while(!pQueue.empty()){
        int nod = pQueue.top().second;
        pQueue.pop();
        inApm.at(nod) = true;
        for(auto& elem:graph.at(nod)){
            if(inApm.at(elem.first)==false){
                if(key.at(elem.first)> elem.second){
                    key.at(elem.first) = elem.second;
                    parent.at(elem.first) = nod;
                    pQueue.push(make_pair(elem.second, elem.first));
                }
            }
        }

    }
}

int main()
{
    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));
    }

    apm();

    long long cost = 0;

    for(int i=2; i<=n; i++){
        cost+= key.at(i);
    }
    fout<<cost<<"\n";
    fout<<n-1<<"\n";

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