//
//*Source developed by BlackBird_v.1.0
//
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
 
#define st second.first
#define dr second.second
#define cost first
#define pb push_back
#define mp make_pair
 
vector < pair <int, pair<int,int> > > V;
int n,m,a,b,c,sol(0),suma(0);
int Root[200013],X[400013],Y[400013];
 
inline bool comp( pair <int, pair<int,int> > a, pair <int, pair<int,int> > b)
{
 return (a.cost<b.cost);
}
 
inline int Find_root( int nod ) 
{
 if (Root[nod]==nod) return nod;
 return Root[nod]=Find_root(Root[nod]);
}
 
inline int cicle( int a, int b ) 
{
 if (a==b) return 1;
 return 0;
}
 
void add_sol(int a,int b, int c)
{
 ++sol; 
 suma+=c;
 X[sol]=a;
 Y[sol]=b;   
}
 
void unite ( int a, int b)
{
 if (a!=b) Root[b]=a;
}
 
void kruskal()
{
 sort(V.begin(),V.end(),comp);    
 for (int i=0;i<V.size();++i)
  {
   int r1=Find_root(V[i].st);
   int r2=Find_root(V[i].dr);
   if (!cicle(r1,r2))
         {
          add_sol(V[i].st,V[i].dr,V[i].cost);
          unite(r1,r2);
         }                                         
  }     
}
 
void print_solution()
{
 cout<<suma<<"\n";
 cout<<sol<<"\n";
 for (int i=1;i<=sol;++i) cout<<Y[i]<<" "<<X[i]<<"\n";
}
 
inline void initialize_root()
{
 for (int i=1;i<=n;++i) Root[i]=i;
}
 
int main()
{
 cin>>n>>m;
 initialize_root();
 while(m--)
  {
    cin>>a>>b>>c;
    V.pb(mp(c,mp(a,b)));             
  }
 kruskal();
 print_solution();  
return 0;
}