#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXBOX = 100000;
const int MAXBALL = 100000;
const int MAXCYC = MAXBOX;

int nbox, nball;
int a[MAXBALL], b[MAXBALL], c[MAXBALL];

int who[MAXBOX];
int state[MAXBOX];
int cyc[MAXBOX], ncyc;
bool isspecial[MAXBALL];
bool isolated[MAXCYC];
int cyclen[MAXCYC];

int solve() {
	REP(i, nball) isspecial[i] = false;
	REP(i, nbox) who[i] = -1;
	REP(i, nball) if (who[b[i]] == -1) who[b[i]] = i, isspecial[i] = true;
	REP(i, nbox) assert(who[i] != -1);
	REP(i, nbox) state[i] = 0;
	ncyc = 0;
	REP(i, nbox) cyc[i] = -1;
	REP(i, nbox) if (state[i] == 0) {
		int at = i;
		while (state[at] == 0) { state[at] = 1; at = a[who[at]]; }
		if (state[at] == 1) { cyclen[ncyc] = 0; while (state[at] == 1) { state[at] = 2; cyc[at] = ncyc; at = a[who[at]]; ++cyclen[ncyc]; } ++ncyc; }
		at = i; while (state[at] == 1) { state[at] = 3; at = a[who[at]]; }
	}
	//printf("cyc:"); REP(i, nbox) printf(" %d", cyc[i]); puts("");
	REP(i, ncyc) isolated[i] = true;
	REP(i, nball) if (cyc[a[i]] != -1 && cyc[b[i]] == -1) isolated[cyc[a[i]]] = false;
	REP(i, nball) if (!isspecial[i]) { if (cyc[a[i]] != -1) isolated[cyc[a[i]]] = false; if (cyc[b[i]] != -1) isolated[cyc[b[i]]] = false; }

	int cntisolated = 0; REP(i, ncyc) if (isolated[i] && cyclen[i] >= 2) ++cntisolated;
	vector<int> singles; REP(i, nball) if (cyc[a[i]] != -1 && isolated[cyc[a[i]]] && cyclen[cyc[a[i]]] == 1) if (c[i] - 2 >= 1) singles.PB(c[i] - 2); sort(singles.rbegin(), singles.rend());
	int havefree = 0; vector<int> havepay; REP(i, nball) if (cyc[a[i]] == -1 || !isolated[cyc[a[i]]]) if (a[i] != b[i]) havefree += c[i] - 1; else if (c[i] - 1 >= 1) havepay.PB(c[i] - 1); sort(havepay.rbegin(), havepay.rend());
	int extra = 0; REP(i, nball) if (cyc[a[i]] != -1 && isolated[cyc[a[i]]] && cyclen[cyc[a[i]]] >= 2) { assert(a[i] != b[i]); extra += c[i] - 1; }
	int cntchange = 0; REP(i, nball) if (a[i] != b[i]) ++cntchange;

	if (cntisolated == 0) return cntchange;
	if (havefree == 0 && SZ(havepay) == 0) return -1;

	int ret = cntchange + cntisolated;
	int have = havefree;
	if (havefree == 0) { assert(SZ(havepay) >= 1); have += havepay[0]; ++ret; havepay.erase(havepay.begin()); }
	have += extra;
	if (have >= cntisolated) return ret;
	int need = cntisolated - have;
	// we can take an item from singles at cost 2, or from havepay at cost 1
	vector<int> prefsum(SZ(havepay) + 1); prefsum[0] = 0; REPSZ(i, havepay) prefsum[i + 1] = prefsum[i] + havepay[i];
	int best = INT_MAX, cur = 0, at = SZ(havepay);
	REPE(i, SZ(singles)) {
		while (at - 1 >= 0 && prefsum[at - 1] >= need) --at;
		if (prefsum[at] >= need) best = min(best, cur + at);
		if (i < SZ(singles)) {
			need = max(0, need - singles[i]);
			cur += 2;
		}
	}
	if (best == INT_MAX) return -1;
	return ret + best;
}

void run() {
	scanf("%d%d", &nbox, &nball);
	REP(i, nball) scanf("%d%d%d", &a[i], &b[i], &c[i]), --a[i], --b[i];
	printf("%d\n", solve());
}

void stress() {
	REP(rep, 10000000) {
		nbox = rnd() % 5 + 1;
		nball = rnd() % 5 + nbox;
		REP(i, nball) a[i] = rnd() % nbox, b[i] = i < nbox ? i : rnd() % nbox, c[i] = rnd() % 3 + 1;
		solve();
		if (rep % 1000 == 0) printf(".");
	}
}

int main() {
	run();
	//stress();
	return 0;
}


Measured memory_bytes: 6616