#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>


using namespace std;

// Kruskal

bool cmp(pair<pair<int, int>, int> x, pair<pair<int, int>, int> y){

    return x.second < y.second;
}

int find_compress(int x, vector<int>& forest){

    int root = x, parent;
    while(root != forest[root])
        root = forest[root];

    while(forest[x] != root){
        parent = forest[x];
        forest[x] = root;
        x = parent;
    }

    return root;
}

void reuninion(int x, int y, vector<int>& forest, vector<int>& sizes){

    x = find_compress(x, forest);
    y = find_compress(y, forest);
    if(x == y)
        return;
    if(sizes[x] < sizes[y])
        swap(x, y);

    sizes[x] += sizes[y];
    forest[y] = x;
}

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

    int N, M;
    cin >> N >> M;

   vector<pair<pair<int, int>, int>> Edges;
   vector<int> forest, sizes;

   for(int i = 0; i < N; ++i){
       forest.push_back(i);
       sizes.push_back(1);
   }
   


   for(int x, y, c; M > 0; --M){
       cin >> x >> y >> c;
       --x; --y;
       Edges.push_back(make_pair(make_pair(x, y), c));
   }

   vector<pair<int, int>> APM;
   int cost = 0;

   sort(Edges.begin(), Edges.end(), cmp);
    for(auto edge : Edges)
        if(find_compress(edge.first.first, forest) != find_compress(edge.first.second, forest)){
            APM.push_back(edge.first);
            cost += edge.second;
            reuninion(edge.first.first, edge.first.second, forest, sizes);
        }
    cout << cost << "\n";
    cout << APM.size() << "\n";
    for(auto edge : APM)
        cout << edge.first + 1 << " " << edge.second + 1 << "\n";
    
    cin.close();
    cout.close();

    return 0;
}