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

ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int MAXN=2e5+5;

int n, m, rez, tata[MAXN], s[MAXN];
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> ans;

int root(int node){
    if (tata[node]==node)
        return node;
    return tata[node]=root(tata[node]);
}

bool same(int a, int b){
    a=root(a);
    b=root(b);
    return a==b;
}

void unite (int a, int b){
    a=root(a);
    b=root(b);
    if (s[a]<s[b])
        swap(a, b);
    tata[b]=a;
    s[a]+=s[b];
}

int main()
{
    fin>>n>>m;
    for (int i=1;i<=m;++i){
        int a, b, c;
        fin>>a>>b>>c;
        edges.push_back({c, a, b});
    }
    for (int i=1;i<=n;++i){
        tata[i]=i;
        s[i]=1;
    }
    sort(edges.begin(), edges.end());
    for (auto u:edges){
        int a=get<1>(u), b=get<2>(u), c=get<0>(u);
        if (!same(a, b)){
            unite(a, b);
            rez+=c;
            ans.push_back({a, b});
        }
    }
    fout<<rez<<'\n';
    fout<<n-1<<'\n';
    for (auto u:ans){
        fout<<u.first<<' '<<u.second<<'\n';
    }
    return 0;
}