import sys input = sys.stdin.readline sys.setrecursionlimit(10**5+100) from collections import * def bfs(): dist = [-1]*(N+1) dist[0] = 0 q = deque([0]) while q: v = q.popleft() for nv in g[v]: if dist[nv]==-1: dist[nv] = dist[v]+1 q.append(nv) return dist def rbfs(): dist = [-1]*(N+1) dist[N] = 0 q = deque([N]) while q: v = q.popleft() for nv in rg[v]: if dist[nv]==-1: dist[nv] = dist[v]+1 q.append(nv) return dist def dfs(v, pv): global cycle seen[v] = True for nv in g[v]: if dist1[nv]==-1 or dist2[nv]==-1: continue if finished[nv]: continue if seen[nv] and not finished[nv]: cycle = True return dfs(nv, v); if cycle: return finished[v] = True N, M = map(int, input().split()) G = [[] for _ in range(N+1)] g = [[] for _ in range(N+1)] rg = [[] for _ in range(N+1)] for _ in range(M): u, v, l, a = map(int, input().split()) G[u].append((v, l, a)) g[u].append(v) rg[v].append(u) dist1, dist2 = bfs(), rbfs() seen = [False]*(N+1) finished = [False]*(N+1) cycle = False dfs(0, -1) if cycle: print('INF') exit() dpl = [0]*(N+1) dpc = [0]*(N+1) dpc[0] = 1 MOD = 10**9+7 q = deque([0]) while q: nq = deque([]) while q: v = q.popleft() for nv, l, a in G[v]: dpl[nv] += a*dpl[v]+a*dpc[v]*l dpl[nv] %= MOD dpc[nv] += dpc[v]*a dpc[nv] %= MOD nq.append(nv) q = nq print(dpl[N])