#include <fstream>
#include <vector>
#include <algorithm>
#define BufferSize 100000
#define Nmax 200002
#define pii pair<int,int>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int p,n,m,T[Nmax],t,a,b,nr,c,ans;
char buffer[BufferSize];


struct edge{
    int a,b,c;
};
vector<edge> H;

bool digit(int a){return (a<='9' && a>='0');}

void read(int &x){
    char sgn;
    x = 0;
    while (!digit(buffer[p])){
        sgn = buffer[p];
        p++;
        if (p==BufferSize){
            p = 0;
            f.read(buffer,BufferSize);
        }
    }

    while (digit(buffer[p])){
        x = x * 10 + buffer[p] - '0';
        p++;
        if (p==BufferSize){
            p = 0;
            f.read(buffer, BufferSize);
        }
    }
    if (sgn=='-') x *= (-1);
}

int root(int x){
    int rx = x,sav;
    while (T[rx]!=rx) rx = T[rx];
    while (T[x]!=x) sav = T[x],T[x] = rx,x = sav;
    return x;
}

void _union(int x,int y){
    int rx,ry;
    rx = root(x);
    ry = root(y);
    if (rx==ry) return;
    T[rx] = ry;
}

bool _find(int x,int y){
    int rx,ry;
    rx = root(x);
    ry = root(y);
    return rx==ry;
}

bool comp(edge a,edge b){return a.c<b.c;}

vector<pii> res;

int main()
{
    read(n);read(m);
    for(int i=1;i<=n;i++) T[i] = i;
    for (int i=1;i<=m;i++){
        read(a);read(b);read(c);
        H.push_back({a,b,c});
    }

    sort(H.begin(),H.end(),comp);

    for (auto it : H){
        if (nr+1>=n) break;

        if (!_find(it.a,it.b)){
            nr++;
            ans += it.c;
            _union(it.a,it.b);
            res.push_back({it.a,it.b});
        }
    }

    g<<ans<<'\n'<<res.size()<<'\n';
    for (auto it : res) g<<it.first<<' '<<it.second<<'\n';

    return 0;
}