import sys from collections import defaultdict, deque from scipy.sparse.csgraph import connected_components from scipy.sparse import csr_matrix input = sys.stdin.buffer.readline def topological_sort(N, edges): outs = defaultdict(list) ins = defaultdict(int) for v1, v2, in edges: outs[v1].append(v2) ins[v2] += 1 q = deque(v1 for v1 in range(N) if ins[v1] == 0) while q: v1 = q.popleft() yield v1 for v2 in outs[v1]: ins[v2] -= 1 if ins[v2] == 0: q.append(v2) MOD = 10 ** 9 + 7 N, M = map(int, input().split()) edges = [list(map(int, input().split())) for _ in range(M)] # 強連結成分分解により不要部分を削除 edges_set = set((u, v) for u, v, _, _ in edges) edges_set.add((N, 0)) frm, to = [], [] for u, v in edges_set: frm.append(u) to.append(v) matr = csr_matrix(([1] * len(frm), (frm, to)), shape=(N + 1, N + 1)) _, labels = connected_components(matr, connection='strong') l0 = labels[0] if l0 != labels[-1]: print(0);exit() # 弱連結でもない nodes = [i for i, x in enumerate(labels) if x == l0] # 座圧 comp = {x: i for i, x in enumerate(nodes)} N1 = len(comp) succ = [[] for _ in range(N1)] new_edges = set() for u, v, l, a in edges: if u in comp and v in comp: cu, cv = comp[u], comp[v] succ[cu].append((cv, l, a)) new_edges.add((cu, cv)) # トポソ ts = list(topological_sort(N1, new_edges)) if len(ts) != N1: print('INF');exit() assert ts[0] == comp[0] assert ts[-1] == comp[N] dp = [0] * N1 for v in ts: cur = dp[v] for s, l, a in succ[v]: dp[s] += (cur + l) * a dp[s] %= MOD print(dp[ts[-1]])