from atcoder.scc import SCCGraph def main(): n, m = list(map(int, input().split())) scc = SCCGraph(2*n) node = [[] for _ in range(2*n)] inf = 1<<60 for _ in range(m): u, v, w = list(map(int, input().split())) u, v = u-1, v-1 w = 1 if w == 1 else -1 node[2*u].append((2*v+1, w)) node[2*u+1].append((2*v, -1*w)) scc.add_edge(2*u, 2*v+1) scc.add_edge(2*u+1, 2*v) G = scc.scc() inf0 = 1<<30 dp = [-inf0] * 2*n dp[0] = 0 dp[1] = 0 X = [0] * 2*n Y = [-1] * 2*n for gg in G: ff = 1 for u in gg: if dp[u] != -inf0: ff = 0 X[u] = 1 if ff: continue s = gg[0] S = [s] f = 0 while S: u = S.pop() if dp[u] >= inf: f = 1 for v, w in node[u]: if not X[v]: continue if Y[v] == -1: Y[v] = Y[u]+w S.append(v) elif Y[v] != Y[u]+w: f = 1 if f: for u in gg: dp[u] = inf for v, w in node[u]: dp[v] = inf else: t = 0 for u in gg: if dp[u] != -1: t = max(t, dp[u]-Y[u]) for u in gg: dp[u] = t+Y[u] for v, w in node[u]: dp[v] = max(dp[v], dp[u]+w) for u in range(n): ans = max(dp[2*u], dp[2*u+1]) print(ans if ans < inf0 else -1) main()