#include <bits/stdc++.h>
#define nmax 100001
using namespace std;
int h[nmax], tata[nmax];
struct muchie {int x, y, c;};
vector <muchie> q;
int suma;
vector <muchie> sol;
inline bool cmp (muchie a, muchie b)
 {
     return a.c < b.c;
 }
void unire (int x, int y)
{
    if (h[x]>h[y]) tata[y]=x;
    else {tata[x]=y;
    if (h[x]==h[y]) h[y]++;}
}

int gasire (int x)
{
    int r=x;
    while (tata[r]) r=tata[r];
        int y=x, t;
      while (y!=r)
      {
          t=tata[y];
          tata[y]=r;
          y=t;
      }
      return r;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m, i, j, p;
    f >> n >> m;
    int x, y, c;
    int a, b;
    muchie tmp;
    for (i=1; i<=m; ++i)
        {
            f >> tmp.x >> tmp.y >> tmp.c;
            q.push_back(tmp);
        }
        sort (q.begin(),q.end(),cmp);
        for (i=0; i<q.size();++i)
        {
            x=q[i].x;
            y=q[i].y;
            c=q[i].c;
            a=gasire(x);
            b=gasire(y);
            if (a!=b)
            {
                suma+=c;
                tmp.x=x;
                tmp.y=y;
                tmp.c=NULL;
                sol.push_back(tmp);
                unire(a,b);
            }

        }
        g << suma << "\n" << n-1 << "\n";
        for (i=0; i<sol.size();++i)
        {
            g << sol[i].x << " " << sol[i].y << "\n";
        }

    return 0;
}