#include <fstream>
#include<vector>
#include<cstdlib>
#include<utility>
#include<queue>
using namespace std;
struct muchii
{
    int a,b,c;
};
vector <muchii> l;
void quickSort(int left, int right) {

      int i = left, j = right;
      muchii tmp;
      muchii pivot = l[(left + right) / 2];
      while (i <= j)
    {
            while (l[i].c < pivot.c)
                  i++;
            while (l[j].c > pivot.c)
                  j--;
            if (i <= j)
            {
                  tmp = l[i];
                  l[i] = l[j];
                  l[j] = tmp;
                  i++;
                  j--;
            }
      };
      if (left < j)
            quickSort(left, j);

      if (i < right)
            quickSort(i, right);

}
int c[200001];
int gr(int x)
{
    if (x==c[x])
        return x;
    return c[x]=gr(c[x]);
}
int main()
{
    int n,m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    vector <bool> viz;
    int x,y,C;
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>C;
        muchii M;
        M.a=x;
        M.b=y;
        M.c=C;
        l.push_back(M);
    }
    quickSort(0,m-1);
    queue <pair <int ,int> > arb;
    int nr=0;
    long cost=0;
    for(int i=1;i<=n;i++)
        c[i]=i;
    int i=0;
    while(nr!=n-1)
    {
        int g1=gr(l[i].a);
        int g2=gr(l[i].b);
        if(g1!=g2)
        {
            cost+=l[i].c;
            nr++;
            arb.push(make_pair(l[i].a,l[i].b));
            c[g1]=g2;
        }
        i++;
    }
    g<<cost<<"\n"<<n-1<<"\n";
    while(!arb.empty())
    {
        g<<arb.front().first<< " "<<arb.front().second<<"\n";
        arb.pop();
    }
    f.close();
    g.close();
    return 0;
}