#include <bits/stdc++.h>


#define x first
#define y second
#define pb push_back
#define mp make_pair

using namespace std ;

    const int NMAX = 400005 ;
    const int INF = 0x3f3f3f3f;

    typedef pair <int, int> Pair ;
    typedef unsigned long long ull ;
    typedef long long ll ;

    ifstream fin("apm.in") ;
    ofstream fout("apm.out") ;

    struct edge {
    int a, b, c ;
    }me;


   vector <edge> E ;
   int N, M, cost, T[NMAX], sol[NMAX] ;


   bool cmp(edge A, edge B)
   {
       if(A.c < B.c)
        return 1 ;
       return 0 ;

   }

   int grupa_de_cautare(int nod)
   {

       if(nod != T[nod])
        T[nod] = grupa_de_cautare(T[nod]) ;

       return T[nod] ;

   }


   void Runeste(int XX, int YY)
   {
       T[grupa_de_cautare(XX)] = grupa_de_cautare(YY) ;

   }


   inline void Kruskal()
   {
       sort(E.begin(), E.end(), cmp) ;

       for(int i = 1 ; i <= N ; ++ i)
        T[i] = i ;

       for(int i = 0 ; i < M && sol[0] != N - 1 ; ++i)
        if(grupa_de_cautare(E[i].a) != grupa_de_cautare(E[i].b))
            {
                cost += E[i].c ;
                sol[ ++ sol[0]]  = i ;
                Runeste(E[i].a, E[i].b) ;

            }

   }

  int main() {


        fin >> N >> M ;

        for(int  i = 1 ; i <= M ; ++ i)
        {
          fin >> me.a >> me.b >> me.c ;
          E.pb(me) ;

        }

        Kruskal() ;

        fout << cost << '\n' ;
        fout << N - 1 << '\n';

        for(int i = 1 ; i <= sol[0] ; ++ i)
        fout << E[sol[i]].b << ' '<< E[sol[i]].a << '\n' ;


    fin.close() ;
    fout.close() ;
    return 0 ;
}