#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct muchie
{
    int x,y;
    int cost;
    bool operator<(const muchie &u) const
    {
        return cost<u.cost;
    }
};

vector <muchie> u, sol;

int n,m,c[200001];
long int cst=0;

void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
       {
           muchie q;
           scanf("%d%d%d",&q.x,&q.y,&q.cost);
           u.push_back(q);
       }
}


void kruskal()
{
    for(int i=1;i<=n;i++) c[i]=i;
    int i=0,k=0;

    while(sol.size()<n-1)
    {// printf("%d ",i);
        if(c[u[i].x]!=c[u[i].y])
            {
              sol.push_back(u[i]);
              cst+=u[i].cost;
              k++;
              int max,min;
              if(c[u[i].x]<c[u[i].y])
              {
                  max=c[u[i].y];min=c[u[i].x];
              }
              else
              {
                  min=c[u[i].y];max=c[u[i].x];
              }
              for(int j=1;j<=n;j++)
                if(c[j]==max)
                   c[j]=min;
            }
         i++;
    }
}

void afisare()
{

    cout<<cst<<endl<<n-1<<endl;
    for(int i=0;i<n-1;i++)
       printf("%d %d\n",sol[i].x,sol[i].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(u.begin(),u.end());
    kruskal();
    afisare();
    return 0;
}