#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, z, cnt, rez;
pair<int, pair<int, int>> edge[400005];
pair<int, int> sol[200005];

struct ab{
    int root[200005];
    int dim[200005];
}dsu;

void setdsu() {
    for(int i=1; i<=n; i++) {
        dsu.root[i]=i;
        dsu.dim[i]=1;
    }
}

int getroot(int a) {
    if(dsu.root[a]!=a) {
        return getroot(dsu.root[a]);
    }
    return a;
}

void join(int a, int b) {
    a=getroot(a);
    b=getroot(b);
    if(dsu.dim[a]<dsu.dim[b]) {
        int aux=a;
        a=b;
        b=aux;
    }
    dsu.root[b]=a;
    dsu.dim[a]+=dsu.dim[b];
}

bool ok(int a, int b) {
    if(getroot(a)!=getroot(b)) {
        return true;
    }
    return false;
}

int main()
{
    fin >> n >> m;
    setdsu();
    for(int i=1; i<=m; i++) {
        fin >> x >> y >> z;
        edge[i]={z, {x, y}};
    }
    sort(edge+1, edge+m+1);
    for(int i=1; i<=m && cnt<n-1; i++) {
        if(ok(edge[i].second.first, edge[i].second.second)) {
            cnt++;
            rez+=edge[i].first;
            sol[cnt].first=edge[i].second.first;
            sol[cnt].second=edge[i].second.second;
            join(edge[i].second.first, edge[i].second.second);
        }
    }
    fout << rez << "\n" << n-1 << "\n";
    for(int i=1; i<n; i++) {
        fout << sol[i].first << " " << sol[i].second << "\n";
    }
    return 0;
}