#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5 + 10, maxc = 2050, midc = 1010;
vector<pair<int, int>> mucs_by_cost[maxc] = {};
int n, m, tata[maxn] = {}, rk[maxn] = {};
ifstream f("apm.in");
ofstream g("apm.out");

int fnd(const int x){
    return tata[x] ? tata[x] = fnd(tata[x]) : x; }

bool mge(int x, int y){
    x = fnd(x), y = fnd(y);
    if(x == y) return false;
    if(rk[x] > rk[y]) swap(x, y);
    if(rk[x] == rk[y]) ++rk[y];
    tata[x] = y;
    return true; }

int main(){
    f >> n >> m;
    for(int i = 0, x, y, c; i < m; ++i){
        f >> x >> y >> c;
        mucs_by_cost[c + midc].emplace_back(x, y); }
    vector<pair<int, int>> rez;
    long long c = 0;
    for(int i = 0; i < maxc; ++i)
        for(const auto x : mucs_by_cost[i])
            if(mge(x.first, x.second))
                c += i-midc,
                rez.emplace_back(x.first, x.second);
    g << c << '\n' << rez.size() << '\n';
    for(const auto x : rez)
        g << x.first << ' ' << x.second << '\n';
    return 0; }