#include <fstream>
#include <vector>
#include<algorithm>
using namespace std;

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


vector <pair<int, pair <int,int > > > edges ;
int sola[400005],solb[400005];
int n,m;

 int grad[200005];
int fathers[400005];
int find(int x)
{
    if(fathers[x]==x)return x;
    return find(fathers[x]);
}
void uniune (int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx<fy)
        swap(fx,fy);
    fathers[fx]=fy;


}

int main()
{
    int a,b,w;
   f>>n>>m;
   for(int i=1;i<=m;i++)
   {
       f>>a>>b>>w;
       edges.push_back(make_pair(w,make_pair(a,b)));
   }
   for(int i=1;i<=n;i++)
    fathers[i]=i;

   sort(edges.begin(),edges.end());

   int mst_weight=0,mst_edges=0,mst_ni=0;
   while(mst_edges<n-1)
   {
       a=edges[mst_ni].second.first;
       b=edges[mst_ni].second.second;
       w=edges[mst_ni].first;
       if(find(a)!=find(b))
       {
           mst_edges++;
           mst_weight+=w;
           uniune(a,b);
            sola[mst_edges]=a;
            solb[mst_edges]=b;
       }
       mst_ni++;
   }
   g<<mst_weight<<'\n';
    g<<mst_edges<<'\n';
    for(int i=1;i<=mst_edges;i++)
        g<<sola[i]<<' '<<solb[i]<<'\n';
    return 0;
}