#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 int 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=0;j<sets[oldset].size();++j)
                sets[newset].push_back(sets[oldset][j]), find_set[sets[oldset][j]] = find_set[newset];
            sets[oldset].clear();
            mst.push_back({x,y});
            ans+=w;
        }
    }
    printf("%d\n%d\n", ans, mst.size());
    for(int i=0;i<mst.size();++i)
        printf("%d %d\n",mst[i].first, mst[i].second);
    return 0;
}