#include <bits/stdc++.h>

using namespace std;

const string file="apm";
ifstream fin(file+".in");
ofstream fout(file+".out");

int a[200001], sum=0;
int get_set(int x)
{
    if (a[x]==x)return x;
    a[x]=get_set(a[x]);
    return a[x];
}
void join(int x, int y)
{
    x=get_set(x), y=get_set(y);
    a[y]=x;
}
bool joined(int x, int y)
{
    return get_set(x)==get_set(y);
}
set<pair<int, pair<int, int>>> st;
vector<pair<int, int>>v;
int main()
{
    int n, m;
    fin>>n>>m;
    for (int i=1; i<=n; ++i){a[i]=i;}
    while (m--){
        int x, y, c;
        fin>>x>>y>>c;
        st.insert({c, {y, x}});
    }
    for (auto it:st){
        if (!joined(it.second.second, it.second.first)){
            v.push_back(it.second);
            join(it.second.first, it.second.second);
            sum+=it.first;
        }
    }
    fout<<sum<<"\n"<<v.size()<<"\n";
    for (auto p:v){
        fout<<p.first<<" "<<p.second<<"\n";
    }
    return 0;
}