#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 200010;
const int INF = 2147483600;

#define mp make_pair
int sta[MAXN+1],top; bool inq[MAXN+1];
int N,M; int ans; int nowt; int cir[MAXN+1]; bool Go[MAXN+1];
int bel[MAXN+1],sz[MAXN+1]; int col,ed[MAXN+1]; int vis[MAXN+1]; bool flag=0;
vector<pair<int,int> > vec[MAXN+1]; int a[MAXN+1],b[MAXN+1],c[MAXN+1],X; int type[MAXN+1]; 
inline void dfs(int k){
	sz[col]++; vis[k]=++nowt; sta[++top]=k; inq[k]=1;
	for(int i=0,sz=vec[k].size();i<sz;i++){
		int v=vec[k][i].first; if(Go[vec[k][i].second]) continue;
		bel[vec[k][i].second]=col; ed[col]++; Go[vec[k][i].second]=1;
		if(!vis[v]) dfs(v);
		else {
			if(inq[v]) {
				cir[col]=vis[k]-vis[v]+1;
			}
		}
	} inq[k]=0; --nowt;
}
#define pb push_back
vector<int> F[9];

int main(){
	N=read(),M=read();
	for(int i=1;i<=M;i++) {
		a[i]=read(),b[i]=read(),c[i]=read();
		vec[a[i]].pb(mp(b[i],i)); vec[b[i]].pb(mp(a[i],i));
		if(a[i]!=b[i]) ++ans;
		if(a[i]!=b[i]&&!c[i]){
			puts("-1"); return 0;
		}
	}
	for(int i=1;i<=N;i++){
		if(!vis[i]) {
			flag=0; top=0;
			nowt=0; ++col,dfs(i);
			if(cir[col]==sz[col]&&sz[col]==ed[col]&&sz[col]>1){
				 ++ans,++X,type[col]=2;
			}
			else if(sz[col]==1&&ed[col]==1) type[col]=1;
			else type[col]=3;
		}
	}
	for(int i=1;i<=M;i++){
		int tp=type[bel[i]];
		if(tp==1){
			if(c[i]>2) F[1].pb(c[i]-2);//2
		} else if(tp==2){
			if(c[i]>1) F[2].pb(c[i]-1);//0
		} else{
			if(c[i]<=1) continue; 
			if(a[i]==b[i]) F[3].pb(c[i]-1);//1
			else F[4].pb(c[i]-1); //0
		}
	} if(!(F[3].size()+F[4].size())&&X){
		puts("-1"); return 0;
	} if(!X){
		printf("%d\n",ans); return 0;
	}
	//for(int i=1;i<=col;i++) cout<<sz[i]<<" "<<ed[i]<<":"<<type[i]<<endl;
	sort(F[1].begin(),F[1].end());
	reverse(F[1].begin(),F[1].end());
	sort(F[3].begin(),F[3].end());
	reverse(F[3].begin(),F[3].end());
	for(int i=0,sz=F[4].size();i<sz;i++) X-=F[4][i];
	if(!F[4].size()) { ans++,X-=F[3][0],swap(F[3][0],F[3][F[3].size()-1]),F[3].pop_back(); }
	sort(F[3].begin(),F[3].end());
	reverse(F[3].begin(),F[3].end());
	for(int i=0,sz=F[2].size();i<sz;i++) X-=F[2][i];
	int nw1=0,sz1=F[1].size(),sz3=F[3].size(),nowsum=0; LL ret=0,retf=INF;
	while(nw1<sz1&&nowsum<X){
		nowsum+=F[1][nw1]; ret+=2; ++nw1;
	} if(nowsum>=X)
		retf=min(retf,ret);
	for(int i=0;i<sz3;i++){
		nowsum+=F[3][i]; ret++;
		while(nw1-1>=0&&nowsum-F[1][nw1-1]>=X){
			 --nw1; nowsum-=F[1][nw1]; ret-=2;
		} if(nowsum>=X) retf=min(retf,ret);
	} if(retf==INF){ puts("-1"); return 0; }
	printf("%lld\n",retf+ans);
	return 0;
}