//PRIM FARA HEAP ,V. DE DISTANTE
#include <bitset>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=200001;
const int MMAX=400001;
const int inf=2100000000;

int n,m,d[NMAX],viz[NMAX],t[NMAX];
vector <pair<int,int>> muc[NMAX];
vector <pair <int,int>> rasp;

long long cost;
int main()
{
     fin>>n>>m;
     for(int i=1;i<=m;i++)
     {
          int x,y,cost;
          fin>>x>>y>>cost;
          muc[x].push_back(make_pair(y,cost));
          muc[y].push_back(make_pair(x,cost));
     }

     for(int i=1;i<=n;i++)
          d[i]=inf;

     d[1]=0;
     for(int k=1;k<=n;k++)
     {
          int minn,ind;
          minn=inf; ind=-1;

          for(int i=1;i<=n;i++)
               if(!viz[i] && d[i]<minn)
                    minn=d[i], ind=i;

          viz[ind]=1;
          cost+=minn;
          rasp.push_back(make_pair(ind,t[ind]));

          vector <pair<int,int>> ::iterator it;
          for(it=muc[ind].begin(); it!=muc[ind].end(); it++)
          //for(auto it:muc[ind])
               {
                    int cst,y;
                    y=(*it).first;
                    cst=(*it).second;

                    if(!viz[y] && d[y]>cst)
                         d[y]=cst, t[y]=ind;
               }
     }
     fout<<cost<<'\n'<<n-1<<'\n';
     for(int i=1;i<rasp.size();i++)
          fout<<rasp[i].first<<' '<<rasp[i].second<<'\n';
    return 0;
}