#include <bits/stdc++.h>

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
const int NMAX=2e5+5;
int P[NMAX],x,y,c,n,m,cost,cx,cy,q;
struct muchie{
    int x;
    int y;
    int c;
} G[NMAX],APM[NMAX];

int cmp(muchie x, muchie y)
{
    return (x.c<y.c);
}
void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>G[i].x>>G[i].y>>G[i].c;

}
int radacina(int nod)
{
    while(P[nod]!=nod)
        nod=P[nod];
    return nod;
}
int dfs(int nod)
{
    if(P[nod]!=nod)
    P[nod]=dfs(P[nod]);
    return P[nod];
}
void rezolvare()
{
    sort(G+1,G+m+1,cmp);
    for(int i=1;i<=n;i++) P[i]=i;
    for(int i=1;i<=m;i++)
    {
        cx=radacina(G[i].x);
        cy=radacina(G[i].y);
        dfs(x);
        dfs(y);
        if(cx!=cy)
        {
             cost+=G[i].c;
             APM[++q]=G[i];
             P[cx]=cy;
        }

    }


}

void afisare()
{
    fout<<cost<<'\n'<<q<<'\n';
    for(int i=1;i<=n-1;i++)
        fout<<APM[i].x<<" "<<APM[i].y<<'\n';
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}