#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{int x,y,v;};
muchie a[400001];
bool cmp(muchie a,muchie b)
{
  return a.v<b.v;
}
vector <int> v[100001];
bitset <100001> viz;
int n,m,i,j,sol,ms[100001],nrm;
void dfs(int x)
{
  int j;
  viz[x]=true;
  for (j=0;j<v[x].size();j++)
    if (viz[v[x][j]]==false)
      dfs(v[x][j]);
}
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
      f>>a[i].x>>a[i].y>>a[i].v;
    sort(a+1,a+m+1,cmp);
  for (i=1;i<=m;i++)
    {
      for (j=1;j<=n;j++)
        viz[j]=false;
       dfs(a[i].x);
       if (viz[a[i].y]==false)
        ms[++nrm]=i,sol+=a[i].v,v[a[i].x].push_back(a[i].y),v[a[i].y].push_back(a[i].x);
    }
    g<<sol<<'\n';
    g<<nrm<<'\n';
    for (i=1;i<=nrm;i++)
      g<<a[ms[i]].y<<' '<<a[ms[i]].x<<'\n';
    return 0;
}