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

using namespace std;

struct Muchie {
    int x,y,cost;
    Muchie() {}
    Muchie(int a,int b,int c) {
        x=a,y=b,cost=c;
    }
    bool operator<(const Muchie &other) const {
        return cost < other.cost;
    }
};

const int NMAX = 200000;

vector <Muchie> v;
vector <Muchie> folosit;
int t[NMAX + 5], h[NMAX + 5];

inline int find(int x) {
    while(t[x]!=x)
        x=t[x];
    return x;
}

inline bool unifica(int x,int y) {
    ///x si y sunt radacini de arbori
    if(x==y)
        return 0;
    if(h[x]>=h[y]) {
        t[y]=x;
        h[x]+=(h[x]==h[y]);
        return 1;
    }
    t[x]=y;
    return 1;
}

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        int x,y,cost;
        scanf("%d%d%d",&x,&y,&cost);
        v.push_back(Muchie(x,y,cost));
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
        t[i]=i,h[i]=1;
    for(int i=0; i<m; i++)
        if(unifica(find(v[i].x),find(v[i].y)))
            folosit.push_back(v[i]);
    int sum=0;
    for(int i=0; i<folosit.size(); i++)
        sum+=folosit[i].cost;
    printf("%d\n%d\n",sum,folosit.size());
    for(int i=0; i<folosit.size(); i++)
        printf("%d %d\n",folosit[i].x,folosit[i].y);
}