#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
const int dim=200001;
typedef struct
  int i,M,cntAPM=0,costAPM=0;
//{
//
//    int X,Y,Cost;
//
//}triplet;
vector <pair<int,int> > v[dim];
vector <pair<int,int>> APM[dim];
int *r,N;
void initializare(int u)
{

    r[u]=u;

}
int reprez(int u)
{

    return r[u];

}
void reuneste(int u,int v)

{

    int r1=reprez(u);
    int r2=reprez(v);

    for(int k=1;k<=N;k++)

    {

        if(r[k]==r2)

        {

            r[k]=r1;

        }

    }

}
void Prim(int nod_start)
{
    for(i=0;i<v[nod_start].size();i++)
    {
          if(reprez(nod_start)!=reprez(v[nod_start][i].first))
          {
            costAPM+=v[nod_start].second;
            APM.push_back(make_pair(nod_start,v[nod_start]));
            reuneste(nod_start,v[nod_start][i].first);
          }
    }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>N>>M;
    r=new int[N+1];
    int *r;
    for(i=0;i<M;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));

    }
    for(i=1;i<=N;i++)
    {
        sort(v[i].begin(),v[i].begin()+v[i].size());
    }
    //sort(v.begin(),v.begin()+M,myFunction);
    for(i=1;i<=N;i++)
    {
        initializare(i);
    }
    Prim(1);
    fout<<costAPM<<'\n';
    fout<<APM.size()<<'\n';
    for(i=0;i<APM.size();i++)
    {
        fout<<APM[i].X<<' '<<APM[i].Y<<'\n';
    }
    fin.close();
    fout.close();
    return 0;

}