#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define N 200005
#define pinf 5000030000
using namespace std;

long long D[N],cost;
int T[N],n,m;
bool S[N];

class Compar
{
 public:
 bool operator()( pair<int,int> x, pair<int,int> y)
 {
    return x.second>y.second; // ordine crscatoare
 }
};

priority_queue< pair< int,int >, vector< pair<int,int> >, Compar > coada;
vector <vector< pair< int, int> > >L(N);

ifstream f("apm.in");
ofstream g("apm.out");

void prim(int r)
{
    int i,poz,c,k=0;

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

    coada.push(make_pair(r,0));D[r]=0;

    int j=0;
    while(j<n) //selectam n noduri
    {

        poz=coada.top().first;
        c=coada.top().second;
        coada.pop();

        if(D[poz]==c && !S[poz])  //adaugam la subarbore pe poz
        {
           cost+=D[poz];
           S[poz]=true;
          //parcurgem lista de adiacenta a lui poz
          for(i=0;i<L[poz].size();i++)
            if(D[L[poz][i].first]>L[poz][i].second ) //daca putem imbunatati distanta
            {
                D[L[poz][i].first]=L[poz][i].second;
                T[L[poz][i].first]=poz;
                coada.push(make_pair(L[poz][i].first,D[L[poz][i].first]));
                   //adaugam nodul si distanta imbunatatita in coada
            }
            j++;
        }
    }

}

int main()
{
   int x,y,c,i;
   f>>n>>m;
   for(i=1;i<=m;i++)
   {
      f>>x>>y>>c;
      L[x].push_back(make_pair(y,c));
      L[y].push_back(make_pair(x,c));
   }

   prim(1);
   g<<cost<<"\n"<<n-1<<"\n";
   for(i=2;i<=n;i++)
    g<<i<<" "<<T[i]<<"\n";


   f.close();
   g.close();
   return 0;
}