#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>

#define next_node adc[curr][i].first
#define distance adc[curr][i].second
using namespace std;
const auto NMAX = 200005, MMAX = 400005;
const int inf = 1<<29;

struct edge{
    int x, y, w;
}v[MMAX+5];
bool cmp(edge a, edge b){
    return a.w<b.w;
}

vector<int> sets[NMAX+5];
vector<pair<int,int>> mst;
int find_set[NMAX+5];
int n, m, ans;

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&v[i].x, &v[i].y, &v[i].w);
    for(int i=1;i<=n;++i)
        sets[i].push_back(i), find_set[i] = i;
    sort(v+1,v+m+1, cmp);
    for(int i=1;i<=m;++i){
        int x= v[i].x, y= v[i].y, w= v[i].w;
        if(find_set[x] == find_set[y])
            continue;
        else{
            int oldset = find_set[y], newset = find_set[x];
            for(int j : sets[oldset]) {
                find_set[j] = find_set[newset];//++++sets[newset].push_back(sets[oldset][j])
            }
            sets[newset].insert(sets[newset].end(), make_move_iterator(sets[oldset].begin()), make_move_iterator(sets[oldset].end()));
            sets[oldset].erase(sets[oldset].begin(), sets[oldset].end());
            mst.emplace_back(x,y);
            ans+=w;
        }
    }
    printf("%d\n%d\n", ans, mst.size());
    for(auto & i : mst)
        printf("%d %d\n",i.first, i.second);
    return 0;
}