#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector <pair<int,pair<int,int>>> muc;
int n, m, t[200005], rez, x, y, c;
vector <pair<int,int>> sol;

int cauttata(int nod){
    if(t[nod] == 0)
        return nod;
    t[nod] = cauttata(t[nod]);
    return t[nod];
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d%d", &n,&m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d", &x,&y,&c);
        muc.push_back({c,{x,y}});
    }

    sort(muc.begin(), muc.end());

    for(auto i : muc){
        int tx = cauttata(i.second.first), ty = cauttata(i.second.second);
        if(tx!=ty){
            sol.push_back(i.second);
            rez+=i.first;
            t[tx] = ty;
        }
    }

    cout<<rez<<"\n"<<n-1<<"\n";
    for(auto i : sol)
        cout<<i.first<<" "<<i.second<<"\n";

    return 0;
}