//#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
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);
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
  cost=1001;

  scanf("%d %d", &n, &m);
  for (i=1;i<=m;i++)
  {
    scanf("%d%d%d", &x, &y, &c);//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;
    }
  }
  printf("%d\n%d\n", cost, n-1);
  for (auto i: v)
  {
  	printf("%d %d\n", i.first, i.second);
    //fout<<i.first<<" "<<i.second<<'\n';
  }
  printf("\n");
  return 0;
}