#include<fstream>
#include<queue>
#include<vector>
#define NMAX 200001
#define MMAX 400001

using namespace std;

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

class muchie
{
public:
  int first,second;
  short cost;
  friend bool operator<(muchie m1,muchie m2);

};

bool operator<(muchie m1, muchie m2)
{
     if(m1.cost>m2.cost)
        return true;
     return false;
}

priority_queue<muchie> heap;
vector<muchie> muchii;
int tata[NMAX], rang[NMAX];
int n,m,k,i,nrMuchii=0;
long long cost;

int findRoot(int x)
{
    int root,aux;
    root=x;
    while(root!=tata[root])
        root=tata[root];
  //  g<<x<<" "<<root<<'\n';
    while(x!=root)
    {
        aux=tata[x];
        tata[x]=root;
        x=aux;
    }
    return root;
}

void unite(int x,int y)
{
    if(rang[x]<rang[y])
        tata[x]=y;
    else
        tata[y]=x;

    //g<<x<<" "<<rang[x]<<"   "<<y<<" "<<rang[y];

    if(rang[x]==rang[y])
        {rang[x]++;/*g<<" DA";*/}
    //g<<'\n';
}

void solve()
{
    int fr1,fr2;
    muchie mc;
    while(!heap.empty())
    {
        //g<<(heap.top()).cost<<" ";

        mc=heap.top();heap.pop();
        fr1=findRoot(mc.first); fr2=findRoot(mc.second);
        if(fr1!=fr2)
          {
            //  g<<mc.first<<" "<<mc.second<<" "<<mc.cost<<'\n';
              cost+=mc.cost; unite(fr1,fr2);
              nrMuchii++;
              muchii.push_back(mc);
          }
    }
}

int main()
{
    int c,x,y;
    muchie edge;
    f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        tata[x]=x; tata[y]=y; rang[x]=rang[y]=1;
        edge.first=x; edge.second=y; edge.cost=c;
        heap.push(edge);
    }
    solve();
    g<<cost<<'\n';
    g<<nrMuchii<<'\n';
    for(i=0;i<muchii.size();i++)
    {
        g<<muchii[i].first<<" "<<muchii[i].second<<'\n';
    }
    f.close();g.close();
    return 0;
}