#include<fstream>
#include<vector>
#include<algorithm>
#define maxM 400001
#define maxN 100001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muc{
    int x,y,c;

}v[maxM];

int h[maxN],t[maxN],tata[maxN],n,m;
vector<int>sol;
bool cmp(muc a,muc b)
{
    return a.c<b.c;
}
void citire()
{   int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,cmp);
}
int rad(int a)
{
    while(t[a])
        a=t[a];
    return a;
}
void uneste(int a,int b)
{
    if(h[a] == h[b] )
        {
            t[b] = a;
            h[a] ++;
        }
    else
        if(h[a] < h[b])
            t[a] =b;
        else t[b] =a;
}
void kruskal()
{   int cost_total = 0 , i,k=1,radx,rady;
    i=1;
   while(k<n)
   {
     radx = rad(v[i].x);
     rady = rad(v[i].y);
     if(radx != rady )
     {
         uneste(radx,rady);
         sol.push_back(i);

         cost_total += v[i].c;
         k++;
     }
     i++;
   }
   g<<cost_total<<'\n';
   g<<n-1<<'\n';
   for(i=0;i<sol.size();i++)
     g<< v[sol[i]].x << " "<<v[sol[i]].y<<'\n' ;
}
int main()
{
    citire();
    kruskal();
    return 0;
}