#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,c;
vector <pair<int,int>> edges[2001];
vector <pair<int,int> >mst_edges;
vector < set <int> > mst;
void read()
{
	fin>>n>>m;
	for(int i=1;i<=m;i++) 
	{
		fin>>x>>y>>c;
		edges[c+1000].push_back(make_pair(x,y));
	}
}
void slove()
{
	set <int> s;
	for(int i=1;i<=n;i++)
	{
		s.clear();
		s.insert(i);
		mst.push_back(s);
	}
	for(int i=0;i<n;i++)
	{
     }
	int cost=0,edge_count=0;
	int ppp=0;

		for(int i=0;i<=2000;i++)
		{
			if(edges[i].size()!=0)
			{
				for(int j=0;j<edges[i].size();j++)
				{
					int x=edges[i][j].first;
					int y=edges[i][j].second;
					int posx=-1,posy=-1;
					for(int k=0;k<mst.size();k++)
						if(mst[k].find(x)!=mst[k].end()) {posx=k; break;}
					for(int k=0;k<mst.size();k++)
						if(mst[k].find(y)!=mst[k].end()) {posy=k; break;}
					if(posx!=posy&&posx!=-1&&posy!=-1)
					{
						mst_edges.push_back(make_pair(x,y));
						cost+=i-1000;
                        mst[posx].insert(mst[posy].begin(),mst[posy].end());
						mst[posy].erase(mst[posy].begin(),mst[posy].end());
						edge_count++; if(edge_count==n-1) 
						{
							fout<<cost<<'\n'<<n-1<<'\n';
							for(int k=0;k<mst_edges.size();k++)
								fout<<mst_edges[k].first<<' '<<mst_edges[k].second<<'\n';
							return;
						}
					}
				}
			}
		}
}
int main()
{
    read();
    slove();
	return 0;
}