#include <bits/stdc++.h>
#define DM 200005
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
struct edge{
int x;int y;int c;
} E[2*DM];
int nr;
bool cmp(edge a,edge b)
{
    return a.c<b.c;
}
queue <int> q;
int c;
int n,m;
int C[DM];
int nextnode()
{
    int pas=1;
    while(1)
    {
        if(C[E[pas].x]==1)
        {
            if(C[E[pas].y]==0)
            {   q.push(pas);
                c+=E[pas].c;
                return E[pas].y;
            }

        }
        if(C[E[pas].y]==1)
        {
            if(C[E[pas].x]==0)
               {
                   q.push(pas);
                   c+=E[pas].c;
                   return E[pas].x;
               }
        }
        pas++;

    }

}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
    {

        fi>>E[i].x>>E[i].y>>E[i].c;
    }
    C[1]=1;
    nr=1;
    int current=1;

    sort(E+1,E+m+1,cmp);
   /* for(int i=1;i<=m;i++)
    {
        cout<<E[i].x<<' '<<E[i].y<<' '<<E[i].c<<'\n';
    }
  */
    while(nr<n)
    {

        current=nextnode();
        C[current]=1;
        nr++;
    }
    fo<<c<<'\n'<<n-1<<'\n';
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        fo<<E[top].x<<' '<<E[top].y<<'\n';
    }

    return 0;
}