// // ------------------------------KRUSKAL APCM

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

// ifstream cin("apm.in");
// ofstream cout("apm.out");

// int n, m, x, y, c;
// int i;
// int cost_total=0;
// vector <int> tata;
// vector<pair<int, int>> muchii_apcm;
// vector <int> inaltime;

// struct Muchie{
//     int x,y; //capetele muchiei
//     int c; //costul muchiei

//     bool operator<(const Muchie& other) const {
//         return c < other.c;
//     }
// };

// vector<Muchie> muchii;

// void citire(){
//     cin>>n>>m;
//     for(i=1; i<= m; i++){
//         cin>>x>>y>>c;
//         muchii.push_back({x,y,c});
//     }
// }

// void ordonare_muchii(){
//     sort(muchii.begin(), muchii.end());
// }

// void initializare_tata(){
//     inaltime.resize(n + 1, 0);
//     tata.resize(n + 1);
//     for(i=1; i<=n ;i++){
//         tata[i]=i;
//     }
// }

// int Find(int nod){
//     if(tata[nod]==nod)
//         return nod;
//     return tata[nod] = Find(tata[nod]);
// }

// void Union(int x, int y){
//     int radacina_x = Find(x);
//     int radacina_y = Find(y);
//     if (radacina_x != radacina_y)
//     {
//         if(inaltime[radacina_x]< inaltime[radacina_y]){
//             tata[radacina_x]=radacina_y;
//         }else if(inaltime[radacina_x]> inaltime[radacina_y]){
//             tata[radacina_y]=radacina_x;
//         }else{
//             tata[radacina_x]=radacina_y;
//             inaltime[radacina_y]++;
//         }
        
//     }
// }

// void Kruskal_APCM(){
//     citire();
//     ordonare_muchii();
//     initializare_tata();

//     for( const auto& muchie : muchii){
//         int radacina_x= Find(muchie.x);
//         int radacina_y= Find(muchie.y);

//         if(radacina_x != radacina_y){
//             cost_total+=muchie.c;
//             muchii_apcm.push_back({muchie.x, muchie.y});
//             Union(muchie.x, muchie.y);

//             if(muchii_apcm.size() == n-1){
//                 break;
//             }
//         }
//     }
// }

// void afisare(){
//     cout<< cost_total<<endl;
//     cout<<muchii_apcm.size()<<endl;

//     for( const auto& muchie: muchii_apcm){
//         cout<< muchie.first <<" "<<muchie.second<<endl;
//     }
// }

// int main(){

//     Kruskal_APCM();
//     afisare();

//     return 0;
// }


// ------------------------------PRIM APCM

// COMPILARE !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

// C:\msys64\ucrt64\bin\g++ lab3.cpp -o lab3.exe -LC:\msys64\ucrt64\lib
// .\lab3.exe


// #include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");



int n,m,x,y,c;
int i;
int cost_total, nr_total_muchii, nr_noduri_adaugate;

vector <pair<int, int>> muchii_apcm;
vector <bool> noduri_in_apcm;

struct Muchie{
    int x,y;
    int c;

bool operator<(const Muchie& other) const{
    return c<other.c;
}
};

vector <vector <pair<int, int>>> graf;// perechea: {nod vecin, cost} pt fiecare nod, si le salvam in vector


void citire(){
    cin>>n>>m;

    graf.resize(n+1);
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        graf[x].push_back({y,c});
        graf[y].push_back({x,c});
    }
}

void initializare(){
    noduri_in_apcm.resize(n+1, false);
    cost_total = 0;
    nr_total_muchii = 0;
    nr_noduri_adaugate= 0;
    noduri_in_apcm[1]=true;//pornim de la nodul 1, il bifam vizitat
    nr_noduri_adaugate=1;
}

void Prim_APCM(){

    citire();
    initializare();

    while(nr_noduri_adaugate < n)
    {
        int cost_minim= INT_MAX;
        int nod1 = 0;
        int nod2 = 0;// noile capete ale muchiei de adaugat


        for(int nod=1;nod<=n;nod++)
        {
            if(noduri_in_apcm[nod])
            {
                for(auto vecin : graf[nod])
                {
                    int v = vecin.first;
                    int cost = vecin. second;

                    if(!noduri_in_apcm[v] && cost< cost_minim)
                    {
                        cost_minim = cost;
                        nod1 = v;
                        nod2 = nod;
                    }
                }
            }
        }

        if(nod1!=0 && nod2!=0)
        {
            if(nod2 < nod1)
            {
                muchii_apcm.push_back({nod2, nod1});
            }
            else
            {
                muchii_apcm.push_back({nod1, nod2});
            }

            noduri_in_apcm[nod1] = true;
            cost_total+=cost_minim;
            nr_total_muchii++;
            nr_noduri_adaugate++;
        }
    }
}

void afisare(){
    cout<<cost_total<<endl;
    cout<<nr_total_muchii<<endl;
    for(auto muchie :muchii_apcm){
        cout<<muchie.first<<" "<<muchie.second<<endl;
    }
    
}

int main(){

    Prim_APCM();
    afisare();

    return 0;
}