#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;

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

typedef pair<int,pair<int,int>> iPPair;

int n, m, k, cnt, total;
vector<iPPair> G;
vector<int> Rang;
vector<int> T;
vector<pair<int,int>> Ans;



void print(){
    cout << total << '\n'
         << n - 1 << '\n';
    for(auto i:Ans)
        cout << i.first << ' ' << i.second << '\n';
}

int root(int node){
    while(T[node]!=node)
        node = T[node];
    return node;
}
void Union(int x,int y){
    if(Rang[x]<Rang[y])
        T[x] = y;
    else if(Rang[x]>Rang[y])
        T[y] = x;
    else
        T[x] = y,
        Rang[y]++;
}

void kruskal(){
    for (auto i:G){
        int x = root(i.second.first);
        int y = root(i.second.second);
        if(x!=y){
            total += i.first;
            Ans.push_back(make_pair(i.second.first, i.second.second));
            Union(x, y);
        }
    }
}

void read(){
    cin >> n >> m;
    T = Rang=vector<int>(n + 1);
    for (int x, y, w, i = 1; i <= m;i++)
        cin >> x >> y >> w,
        G.push_back(make_pair(w, make_pair(y, x))),
    sort(G.begin(), G.end());
    for (int i = 1; i <= n;i++)
        T[i] = i,
        Rang[i] = 1;
}
void solve(){
    read();
    kruskal();
    print();
}

int main(){
    solve();
    return 0;
}