#include <bits/stdc++.h>
#define nmax 20000
#define inf 5000
//prim fara heap
int n, r, i, vfmin, nrv;
short int g[nmax][nmax];
short int p[nmax], z[nmax];
short int cmin[nmax], costmin;

using namespace std;

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int m;
    int i, a, b, j, k;
    fin >> n >> m;
    r=1;

    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        g[i][j]=inf;

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

    for (i=1;i<=m;++i)
    {
    fin >> a >> b >> k;
    g[a][b]=k;
    g[b][a]=k;
    }

    for (i=1;i<=n;++i)
    {
    cmin[i]=g[r][i];
    p[i]=r;
    z[i]=1;
    }
    nrv=n-1;
    z[r]=0;
    p[r]=0;
    while (nrv)
 {
     costmin=inf-1;
     for (i=1;i<=n;++i)
        if (z[i] && costmin>cmin[i])
            {costmin=cmin[i];
                vfmin=i;}

     z[vfmin]=0;
     nrv--;
         for (i=1; i<=n; ++i)
         {
             if (z[i] && g[i][vfmin] < cmin[i])
             {
                 p[i]=vfmin;
                 cmin[i]=g[i][vfmin];
             }
         }


 }


 int cost=0;
      for (i=1;i<=n;++i)
      {
         if (r!=i)
          {
              cost+= g[i][p[i]] ;
          }
      }

fout  << cost << "\n" << n-1 << "\n";
    for (i=1;i<=n;++i)
    {
       if (r!=i)
       {
           fout << p[i] << " " <<  i << "\n";
       }
    }


    return 0;
}