#include<fstream>
#include<algorithm>
using namespace std;

struct muchie {int x,y,cost;};
muchie muc[400010];

int n,m,sol,tata[200010],poz[200010];

bool cmp(muchie A,muchie B) {
    return A.cost<B.cost;
}

int dfs(int nod1) {

    if(nod1!=tata[nod1])
        tata[nod1]=dfs(tata[nod1]);
    return tata[nod1];

}

void citire() {

    ifstream in("apm.in");
    int i;
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>muc[i].x>>muc[i].y>>muc[i].cost;
    in.close();

}

void solve() {

    int i,a,b,nr;
    sort(muc+1,muc+m+1,cmp);
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=1,nr=0;i<=m;i++) {
        a=muc[i].x;
        b=muc[i].y;
        if(dfs(a)!=dfs(b)) {
            tata[dfs(a)]=dfs(b);
            nr++;
            poz[nr]=i;
            sol+=muc[i].cost;

        }
    }

}

void afisare() {

    ofstream out("apm.out");
    int i;
    out<<sol<<'\n';
    out<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        out<<muc[poz[i]].x<<" "<<muc[poz[i]].y<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}