#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,c,i,j,cost,cmin,xmin,ymin;
set<int> s;
vector<pair<int,int>> v;
priority_queue<pair<int,pair<int,int>>> p;
vector<pair<int,int>> g[200001];
int main()
{
	
	ios_base::sync_with_stdio(false);
  cost=1001;
  fin>>n>>m;
  for (i=1;i<=m;i++)
  {
    fin>>x>>y>>c;
    if (c<cost)
    {
      cost=c;
      xmin=x;
      ymin=y;
    }
    g[x].push_back(make_pair(y,-c));
    g[y].push_back(make_pair(x,-c));
    if (s.find(x)==s.end())
      s.insert(x);
    if (s.find(y)==s.end())
      s.insert(y);
  }
  pair<int,pair<int,int>> l;
  v.push_back(make_pair(xmin,ymin));
  s.erase(xmin);
  s.erase(ymin);
  for (auto i: g[xmin])
    //if (s.find(i.first)!=s.end())
      p.push(make_pair(i.second, make_pair(i.first, xmin)));
  for (auto i: g[ymin])
    //if (s.find(i.first)!=s.end())
      p.push(make_pair(i.second, make_pair(i.first, ymin)));
  while (!s.empty())
  {
    l=p.top();
    p.pop();
    if (s.find(l.second.first)!=s.end())
    {
      if (s.find(l.second.second)==s.end())
      {
        for (auto i: g[l.second.first])
        {
          //if (s.find(i.first)!=s.end())
            p.push(make_pair(i.second, make_pair(i.first, l.second.first)));
        }
        v.push_back(make_pair(l.second.first, l.second.second));
        s.erase(l.second.first);
        cost-=l.first;
      }
    }
    else if (s.find(l.second.second)!=s.end())
    {
      for (auto i: g[l.second.second])
        {
          //if (s.find(i.first)!=s.end())
            p.push(make_pair(i.second, make_pair(i.first, l.second.second)));
        }
      v.push_back(make_pair(l.second.first, l.second.second));
      s.erase(l.second.second);
      cost-=l.first;
    }
  }
  fout<<cost<<'\n';
  fout<<n-1<<'\n';
  for (auto i: v)
  {
    fout<<i.first<<" "<<i.second<<'\n';
  }
  fout<<endl;
  return 0;
}