LIM = 32 n, e = map(int, raw_input().strip().split()) # collect graph info back = [None]*n end = [True]*n for i in xrange(e): a, b, l, r = map(int, raw_input().strip().split()) a -= 1; b -= 1; l -= 1; r -= 1 back[b] = a, l, r end[a] = False def traverse(i): ''' yields all nodes from i to 0 ''' while i: yield back[i] i, l, r = back[i] # compute cost[l][r] cost = [[1<<60]*LIM for l in xrange(LIM)] for i in xrange(n): if not end[i]: continue # compute costs for path ending in i. cL = [0]*(LIM+1) cR = [0]*(LIM+1) for curr, l, r in traverse(i): cL[l] += 1 cR[r] += 1 # compute cLL and cRR cLL = [L * v for L, v in enumerate(cL)] cRR = [R * v for R, v in enumerate(cR)] # cumulate for L in xrange(LIM-1,-1,-1): cL[L] += cL[L+1] cLL[L] += cLL[L+1] for R in xrange(1,LIM+1): cR[R] += cR[R-1] cRR[R] += cRR[R-1] # compute cost[l][r] for this path for r in xrange(LIM): c = -(cRR[r] - r * cR[r]); for l in xrange(r+1): cost[l][r] = min(cost[l][r], c + cLL[l+1] - l * cL[l+1]) # dynamic programming best = [0]*(LIM+1) for r in xrange(LIM): best[r+1] = min(best[l] + cost[l][r] for l in xrange(r+1)) print best[LIM]