//Problema 1

// #include <iostream>
// #include <fstream>
// #include <vector>
// using namespace std;
//
// ifstream fin("Laborator.in");
// ofstream fout("Laborator.out");
//
// int findset(vector<int>& tata, int u) {
//     while (tata[u]!=0) {
//         u = tata[u];
//     }
//     return u;
// }
//
// void unionn(vector<int>& tata, vector<int>& h,int u,int v){
//     int a = findset(tata,u);
//     int b = findset(tata,v);
//     if (a!=b) {
//         if (h[a]>h[b]) {
//             tata[b]=a;
//         }
//         else {
//             if (h[b]==h[a]) {
//                 h[b]++;
//             }
//             tata[a] = b;
//
//         }
//     }
// }
//
// int main() {
//
//     int n, m;
//     fin >> n >> m;
//     vector<int> tata(n+1,0);
//     vector<int> h(n+1,0);
//     int o,x,y;
//     for (int i =1;i<=m;++i) {
//         fin >> o >> x >> y;
//         if (o==1) {
//             unionn(tata,h,x,y);
//         }
//         else {
//             if (findset(tata,x)==findset(tata,y)) {
//                 fout<<"DA"<<endl;
//             }
//             else fout<<"Nu"<<endl;
//         }
//     }
//
//     return 0;
//}


// Problema 2 - algortim kruskal

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

ifstream fin("apm.in");
ofstream fout("apm.out");
int findset(vector<int>& tata, int u) {
        while (tata[u]!=0) {
            u = tata[u];
        }
        return u;
    }
void unionn(vector<int>& tata, vector<int>& h,int u,int v){
        int a = findset(tata,u);
        int b = findset(tata,v);
        if (a!=b) {
            if (h[a]>h[b]) {
                tata[b]=a;
            }
            else {
                if (h[b]==h[a]) {
                    h[b]++;
                }
                tata[a] = b;

            }
        }
    }
int main() {
    int n,m;
    fin >> n >> m;
    vector<int> tata(n+1,0);
    vector<int> h(n+1,0);
    vector<pair<int,pair<int,int>>> muchii;

    int x, y, cost;
    for (int i=0;i<m;++i) {
        fin >> x >> y >> cost;
        muchii.push_back({cost,{x,y}});
    }
    sort(muchii.begin(),muchii.end());
    vector<pair<int,int>> s;
    int cost_t = 0;
    for (int i =0;i<m;++i) {
        cost = muchii[i].first;
        x = muchii[i].second.first;
        y = muchii[i].second.second;
        if (findset(tata,x)!=findset(tata,y)) {
            unionn(tata,h,x,y);
            cost_t +=cost ;
            s.push_back({x,y});
            if (s.size()==n-1) {
                break;
            }
        }
    }
    fout<<cost_t<<'\n';
    fout<<s.size()<<'\n';
    for (int i = 0; i < s.size(); ++i) {
        fout<<s[i].second<<" "<<s[i].first<<'\n';
    }
    return 0;
}