#include <bits/stdc++.h>

using namespace std;

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


void read_from_file(){
    ifstream fin("apm.in");

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

    fin.close();
}

priority_queue<pair<int, int>,vector<pair<int,int>>, greater<pair<int, int> > > coada;
vector<bool> inCopac;
vector<int> parinte;
vector<int> cheie;

void apm(int start){
    inCopac.resize(n+1, false);
    cheie.resize(n+1, INT_MAX);
    cheie.at(start) = 0;
    parinte.resize(n+1, -1);
    parinte.at(start) = 1;

    coada.push(make_pair(0, start));

    while(!coada.empty()){
        int nod = coada.top().second;
        inCopac.at(nod) = true;
        coada.pop();

        for(auto& vecin:graph.at(nod)){
            if(!inCopac.at(vecin.first)){

                if(vecin.second <cheie.at(vecin.first)){

                    cheie.at(vecin.first) = vecin.second;
                    coada.push(make_pair(vecin.second, vecin.first));
                    parinte.at(vecin.first) = nod;

                }
            }
        }
    }
}

int main()
{
    read_from_file();
    apm(1);
    ofstream fout("apm.out");



    long long cost = 0;

    for(int i=1; i<=n; i++) cost+=cheie.at(i);

    fout<<cost<<"\n";
    fout<<n-1<<"\n";

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