#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define nmax 400002
const int inf=INT_MAX;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
struct fin{long f,s;}ans[nmax/2];
long n,m,i,c[nmax/2],j,ms,mx,mi,tot,x,y,cs,nr;
vector<pair<long,long> >ap[nmax/2];
vector<pair<long,long> >an[nmax/2];
set<int>s;
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    cin>>n>>m;
    for(i=1;i<=n;i++)c[i]=i;
    for(i=1;i<=m;i++)
	{
		cin>>x>>y>>cs;
		s.insert(cs);
		if(cs<0)an[-cs].push_back({x,y});
		else ap[cs].push_back({x,y});
	}
	set<int>::iterator it;
    for(it=s.begin();it!=s.end();it++)
	{
		if(*it<0)
		 for(i=0;i<an[-*it].size();i++)
		 {
		   if(c[an[-*it][i].first]!=c[an[-*it][i].second])
		   {
			  ans[++ms].f=an[-*it][i].first,ans[ms].s=an[-*it][i].second;
			  tot+=*it;
			  mx=max(c[an[-*it][i].first],c[an[-*it][i].second]);
			  mi=min(c[an[-*it][i].first],c[an[-*it][i].second]);
			  //for(j=1;j<=n;j++)if(c[j]==mx)c[j]=mi;
			  if(ms==n-1)break;
		   }
		 }
		else
		 for(i=0;i<ap[*it].size();i++)
		 {
		 	if(c[ap[*it][i].first]!=c[ap[*it][i].second])
		    {
			  ans[++ms].f=ap[*it][i].first,ans[ms].s=ap[*it][i].second;
			  tot+=*it;
			  mx=max(c[ap[*it][i].first],c[ap[*it][i].second]);
			  mi=min(c[ap[*it][i].first],c[ap[*it][i].second]);
			  //for(j=1;j<=n;j++)if(c[j]==mx)c[j]=mi;
			  if(ms==n-1)break;
			}
		 }
		if(ms==n-1)break;
	}
	cout<<tot<<endl<<ms<<endl;
	for(i=1;i<=ms;i++)cout<<ans[i].f<<" "<<ans[i].s<<endl;
	return 0;
}