/*#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200000;
class Forest{
    public:
}
class Edge{
    public:
        int v1,v2,cost;
        Edge(int vert1,int vert2,int c){
            this->v1=vert1;
            this->v2=vert2;
            this->cost=c;
        }
        bool operator<(const Edge&e)const{
            return this->cost<e.cost;
        }
};
class Adjacent{
    public:
        int v,cost;
};
vector<Adjacent>g[N+1];
Edge e[N+1];
FILE*in,*out;
int n,m;
void scan(){
    int i,v1,v2,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(in,"%d%d",&v1,&v2,c);
        g[v1].push_back();
        e[++noE]=Edge(v1,v2,c);
}
void init(){
    in=fopen("apm.in","r");
    out=fopen("apm.out","w");
    scan();
}
void mst(){
    sort(e+1,e+noE+1);
    for(i=1;i<=m;i++)
        if(set(e[i].v1)==set(e[i].v2))
}
void solve(){
    mst();
}
int main(){
    init();
    solve();
    return 0;
}
*/
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mkp make_pair

using namespace std;

const int maxn = 200200;
const int INF = 200000200;

int VEC[maxn],ANS,V[maxn],H[maxn * 2 + 100],POZ[maxn];
vector <pair<int,int> > VECT[maxn],VANS;
int N,M,L,C[maxn];

void introduce_in_apm(int x)
{
    for(unsigned int i = 0;i < VECT[x].size(); ++i)
    {
        int nod = VECT[x][i].first;
        int cost = VECT[x][i].second;
        V[nod] = min(V[nod],cost);
        if (V[nod] == cost) VEC[nod] = x;
    }
}

void push(int poz)
{
    while((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))
    {
        if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)
        {
            swap(H[poz],H[poz * 2]);
            swap(POZ[H[poz]],POZ[H[poz * 2]]);
            poz *= 2;
        }
        else
        {
            swap(H[poz],H[poz * 2 + 1]);
            swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);
            poz = poz * 2 + 1;
        }
    }
}


void pop(int poz)
{
    while(poz > 1 && V[H[poz]] < V[H[poz / 2]])
    {
        swap(H[poz],H[poz / 2]);
        swap(POZ[H[poz]],POZ[H[poz / 2]]);
        poz = poz / 2;
    }
}

void introduce_in_heap(int nod)
{
    H[++L] = nod;
    POZ[nod] = L;
    pop(L);
}

int scoate_radacina_heap()
{
    int x = H[1];
    swap(H[1],H[L]);
    swap(POZ[H[1]],POZ[H[L]]);
    L--;
    push(1);
        POZ[x] = 0;
    return x;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&N,&M);
    for(int i = 1;i <= M; ++i)
    {
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        VECT[x].pb(mkp(y,c));
        VECT[y].pb(mkp(x,c));
    }

    for(int i = 1;i <= N; ++i) V[i] = INF;
    V[1] = 0;
    introduce_in_apm(1);
    for(int i = 2;i <= N; ++i)
    {
        introduce_in_heap(i);
    }
    for(int i = 1;i < N; ++i)
    {
        int x = scoate_radacina_heap();
        introduce_in_apm(x);
        ANS += V[x];
        VANS.pb(mkp(x,VEC[x]));
        for(unsigned int j = 0;j < VECT[x].size(); ++j)
        {
            int nod = VECT[x][j].first;
            if (POZ[nod]) pop(POZ[nod]);
        }
    }
    printf("%d\n",ANS);
    printf("%d\n",N-1);
    for(unsigned int i = 0;i < N - 1; ++i)
        printf("%d %d\n",VANS[i].first,VANS[i].second);
    return 0;
}