#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int n,m,x,y,c,start,costFinal;
vector <pair <int, int> > graf[200005];
vector <pair <int, int> > raspuns;
char viz[200005];
priority_queue <pair <int, pair <int,int> > > myheap;

void citire () {
    fin>>n>>m;
    for (int i=1; i<=m; i++){
        fin>>x>>y>>c;
        if (i==1){
            start=x;
        }
        pair <int, int> curent;
        curent.first=y;
        curent.second=c;
        graf[x].push_back(curent);
        curent.first=x;
        curent.second=c;
        graf[y].push_back(curent);
    }
}

void prim (int nod){
    /// pusham in heap toate muchiile
    viz[nod]=1;
    int lung=graf[nod].size();
    for (int i=0; i<lung; i++){
        int cost=-graf[nod][i].second;
        int vecin=graf[nod][i].first;
        myheap.push( make_pair(cost, make_pair(nod, vecin)));
    }
    while (!myheap.empty()){
        pair <int, pair <int,int> > curent;
        curent = myheap.top();
        myheap.pop();
        int cost=-curent.first;
        int x=curent.second.first;
        int y=curent.second.second;
        if (viz[y]==0){
            viz[y]=1;
            costFinal+=cost;
            raspuns.push_back(make_pair (x, y));
            int lung=graf[y].size();
            for (int i=0; i<lung; i++){
                myheap.push( make_pair(-graf[y][i].second, make_pair(y, graf[y][i].first)));
            }
        }
    }
}

void afisare (){
    fout<<costFinal<<'\n';
    int lung = raspuns.size();
    fout<<lung<<'\n';
    for (int i=0; i<lung; i++){
        fout<<raspuns[i].first<<' '<<raspuns[i].second<<'\n';
    }
}

int main () {

    citire ();
    prim (start);
    afisare ();
    return 0;
}