#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct muchie {
    int a,b,c;
    muchie() {
        a=b=c=0;
    }
    muchie(int x,int y,int z) {
        a=x;
        b=y;
        c=z;
    }
};

class cmp {
public:
    inline bool operator() (const muchie &a,const muchie &b) {
        return a.c<b.c;
    }
};

const int MAX_N=100100;
const int MAX_M=200100;

int dad[MAX_N];
int h[MAX_N];

vector<muchie> v;
vector<muchie> sol;

int find(int x) {
    if(dad[x]==x) {
        return x;
    }
    return dad[x]=find(dad[x]);
}

void merge(int x,int y) {
    x=find(x);
    y=find(y);

    if(h[x]<h[y]) {
        dad[x]=y;
    }
    else if(h[x]>h[y]) {
        dad[y]=x;
    }
    else {
        dad[x]=y;
        h[x]++;
    }
}

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    v.resize(m);
    for(int i=1;i<=m;i++) { 
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v.push_back(muchie(a,b,c));
    }

    sort(v.begin(),v.end(),cmp());
    for(int i=1;i<=n;i++) {
        dad[i]=i;
        h[i]=1;
    }
    
    int sum=0;

    for(vector<muchie>::iterator it=v.begin(); it!=v.end(); it++) {
        if(find(it->a)!=find(it->b)) {
            sum+=it->c;
            merge(it->a,it->b);
            sol.push_back(*it);
        }
    }


    printf("%d\n",sum);
    printf("%d\n",sol.size());
    for(vector<muchie>::iterator it=sol.begin(); it!=sol.end(); it++) {
        printf("%d %d\n",it->a,it->b);
    }

    return 0;
}