#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

std::ifstream f("grafpond.in");
std::ofstream g("grafpond.out");


int main()
{
    int n, m, nr, cost;
    f>>n>>m;
    std::vector<std::vector<int>> l;
    std::vector<std::vector<int>> lf;
    std::vector<int> rep(n+1);
    for(int x = 1; x <= m; x++)
    {
        int i, j, k;
        f >> i >> j >> k;
        l.push_back({i,j,k});
    }
    std::sort(l.begin(), l.end(), [](const std::vector<int>& a, const std::vector<int>& b)
    { return a[2] < b[2]; });
    for(int x = 1; x <= n; x++)
        rep[x] = x;
    nr = 0;
    cost = 0;
    lf = {};
    for(auto& subl: l)
    {
        if(rep[subl[0]] != rep[subl[1]])
        {
            lf.push_back({subl});
            int oldrep = rep[subl[1]];
            int newrep = rep[subl[0]];
            for(int x = 1; x <= n; x++)
                if(rep[x] == oldrep)
                    rep[x] = newrep;
            nr++;
            if(nr == n - 1)
                break;
        }
    }
    for(auto& subl: lf)
            cost += subl[2];
    g<<cost<<'\n';
    g<<lf.size()<<'\n';
    for(auto& subl: lf)
        g<<subl[1]<<" "<<subl[0]<<" "<<'\n';    
    return 0;
}