#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int L[200010], n,m,x,y,i,j,cost,k,b[200010],p,q;
struct muchie{
int x,y,c;
}M[400010];
int main()
{
    f>>n>>m;

    for(i=1; i<=m; i++)

        f>>M[i].x>>M[i].y>>M[i].c;

    for(i=1; i<=m; i++)

        for(j=i+1; j<=m; j++)

            if(M[i].c> M[j].c) swap(M[i], M[j]);

    for(i=1; i<=n; i++)
        L[i]=i;

    cost=0;

    for(i=1; i<=m; i++)
        if(L[M[i].x] != L[M[i].y]){

        k++;
        b[k]=i;
        cost+=M[i].c;
        p=L[M[i].x];
        q=L[M[i].y];

        for(j=1; j<=n; j++)
            if(L[j]==q)
                L[j]=p;

        if(k==n-1)
        break;}


    g<<cost<<'\n';
    g<<k<<'\n';

    for(i=1; i<=k; i++)
        g<< M[b[i]].y <<' '<< M[b[i]].x<<'\n';

    return 0;
}