#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;
}