#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>
#include <set>
#include <fstream>
using namespace std;

vector <pair <int, int> > adiac[200000];
vector <pair <int,int> > muchii_alese;
int n, m, cost=0, viz[200000], cea_mai_mica_muchie=1001, nod_start;

struct set_compare {
    bool operator() (vector <int> a, vector < int > b) const {
        return a[2]<b[2];
    }
};


void citire () {
    ifstream fin("apm.in");
    fin>>n>>m;
    for (int i=0; i<m; i++) {
        int p1,p2,c;
        fin>>p1>>p2>>c;
        p1--; p2--;
        if (c<cea_mai_mica_muchie) {
            cea_mai_mica_muchie=c;
            nod_start=p1;//aici ii spun de unde sa inceapa; nu conteaza daca iau p1 sau p2
        }
        adiac[p1].push_back(make_pair(p2,c));
        adiac[p2].push_back(make_pair(p1,c));
    }
}

void prim () {
    multiset <vector <int>, set_compare> heap; //bag in heap vectori cu 3 elemente: nod 1, nod 2 si costul;
    viz[nod_start]=1;
    int k=0;
    for (int i=0; i<adiac[nod_start].size(); i++) {
        vector <int> tmp;
        tmp.push_back(nod_start);
        tmp.push_back(adiac[nod_start][i].first);//nodul i la care e adiacent 0
        tmp.push_back(adiac[nod_start][i].second); //costul muchiei dintre 0 si nodul i
        heap.insert(tmp);
    }
    std::multiset <vector <int>, set_compare>::iterator it;
    while (k<n-1) {
        /*cout<<"Iteratia "<<k<<":"<<endl;
        for (int i=0; i<n; i++) {
            cout<<i+1<<" ";
        } cout<<endl;
        for (int i=0; i<n; i++) {
            cout<<viz[i]<<" ";
        }
        cout<<endl;
        for (it=heap.begin(); it!=heap.end(); it++) {
            vector <int> tmp;
            tmp=*it;
            cout<<tmp[0]+1<<" "<<tmp[1]+1<<" "<<tmp[2]<<endl;
        }
        cout<<"cost: "<<cost<<endl;*/
        //*decapitez heap*
        vector <int> tmp;
        it=heap.begin();
        tmp=*it; //tmp e un vector cu 3 elemente
        heap.erase(it);
        //*pun nodul muchiei decapitate in setul vizitatelor; pun muchia decapitata in setul vizitatelor; maresc k*
        k++;
        int cur;
        if (viz[tmp[0]]==0) cur=tmp[0];
        else if (viz[tmp[1]]==0) cur=tmp[1];
        viz[cur]=1;
        muchii_alese.push_back(make_pair(tmp[1], tmp[0]));
        cost+=tmp[2];
        //*adaug la heap muchiile cu 0-1 sau 1-0 din adiacentele nodului cu 0 din muchia decapitata*
        for (int i=0; i<adiac[cur].size(); i++) {
            int nod=adiac[cur][i].first;
            if (viz[nod]==0) { //il introduc in heap ca muchie, adica vector de 3 elemente
                tmp[0]=cur;
                tmp[1]=nod;
                tmp[2]=adiac[cur][i].second; //second e costul, al treilea ca muchie
                heap.insert(tmp);
            }
        }
        //*cat timp radacina e de tip 1-1 decapitez fara sa fac nimic (ignor muchia) *
        if (!(heap.empty())) {
            it=heap.begin();
            tmp=*it;
        }
        while ((viz[tmp[0]]+viz[tmp[1]])==2 && !(heap.empty())) {
            heap.erase(it);
            if (!(heap.empty())) it=heap.begin();
            tmp=*it;
        }
    }

}

int main()
{
    citire();
    for (int i=0; i<n; i++) {
        cout<<i+1<<": ";
        for (int j=0; j<adiac[i].size(); j++) {
            cout<<"("<<adiac[i][j].first+1<<","<<adiac[i][j].second<<")"<<" ";
        }
        cout<<endl;
    }
    cout<<"Incepem de la nodul "<<nod_start+1<<" care are muchia "<<cea_mai_mica_muchie<<endl;
    cout<<"Incepe Prim"<<endl<<endl;
    prim();
    ofstream fout("apm.out");
    cout<<"Cost: "<<cost<<endl;
    fout<<cost<<endl;
    cout<<"Nr. muchii alese: "<<muchii_alese.size()<<endl;
    fout<<n-1<<endl;
    for (int i=0; i<muchii_alese.size(); i++) {
        cout<<muchii_alese[i].first+1<<" "<<muchii_alese[i].second+1<<endl;
        fout<<muchii_alese[i].first+1<<" "<<muchii_alese[i].second+1<<endl;
    }
    return 0;
}