#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

#define dad(x) x>>1
#define fson(x) x<<1
#define sson(x) (x<<1)+1
#define inf 1500

// algoritmul lui prim

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int N,M,costarb;
int h[200010],poz[200010],lung[200010],orig[200010];
bitset<200010> verif;
// h=heap care are cel mai apropriat nod neadaugat in arbore pe pozitia 1
// poz[i]=pozitia in heap a nodului i
// lung[i]=lungimea celui mai mic arc de la nodul i la arborele format
// orig[i]=nodul origine pentru arcul minim de la arbore spre nodul i

struct elem {
    int y,cost;
};
vector<elem> v[200010];
// v=lista de adiacenta

struct elem2 {
    int x,y;
};
vector<elem2> rez;
// rez=vector care retine muchiile solutie

void percolate(int);
void sift(int);

int main()
{
    f>>N>>M;
    FOR (i,1,M) {
        int x,y,cost;
        f>>x>>y>>cost;
        elem A;
        A.y=y;
        A.cost=cost;
        v[x].pb(A);
        A.y=x;
        v[y].pb(A);
    }
    FOR (i,1,N) {
        h[i]=i;
        poz[i]=i;
        lung[i]=inf;
    }
    for (unsigned int k=0;k<v[1].size();++k) {
        lung[v[1][k].y]=v[1][k].cost;
        orig[v[1][k].y]=1;
        percolate(poz[v[1][k].y]);
    }
    verif.set(1,1);
    // pornim de la un arbore format din nodul 1
    while (N-1) {
        int nod=h[1]; // adaugam cel mai apropriat nod la arbore
        verif.set(nod,1);
        costarb+=lung[h[1]];
        elem2 A;
        A.x=orig[h[1]];
        A.y=h[1];
        rez.pb(A);
        swap(h[1],h[N]);
        poz[h[1]]=1;
        --N;
        sift(1);
        for (unsigned int k=0;k<v[nod].size();++k) { // actualizam distantele la noduri ce nu apartin arborelui
            if (!verif.test(v[nod][k].y) && lung[v[nod][k].y]>v[nod][k].cost) {
                lung[v[nod][k].y]=v[nod][k].cost;
                orig[v[nod][k].y]=nod;
                percolate(poz[v[nod][k].y]);

            }
        }
    }
    g<<costarb<<'\n'<<rez.size()<<'\n';
    for (unsigned int k=0;k<rez.size();++k) {
        g<<rez[k].x<<' '<<rez[k].y<<'\n';
    }
    f.close();g.close();
    return 0;
}

void percolate(int x) {
    while (lung[h[x]]<lung[h[dad(x)]] && x!=1) {
        swap(poz[h[x]],poz[h[dad(x)]]);
        swap(h[x],h[dad(x)]);
        x=dad(x);
    }
}

void sift(int x) {
    int son;
    do {
        son=0;
        if (fson(x)<=N) {
            son=fson(x);
            if (sson(x)<=N && lung[h[sson(x)]]<lung[h[fson(x)]]) {
                son=sson(x);
            }
            if (lung[h[son]]>=lung[h[x]]) {
                son=0;
            }
        }
        if (son) {
            swap(poz[h[x]],poz[h[son]]);
            swap(h[x],h[son]);
            x=son;
        }
    }
    while (son);
}