One day, the lord ordered a carpenter to "build a sturdy and large building where the townspeople could evacuate in the event of a typhoon or earthquake." However, large thick pillars are needed to complete the sturdy and large building. There is no such big pillar in the town. So the carpenter decided to go to a distant mountain village to procure a large pillar (the carpenter would have to go from town to satoyama and back in town).

The carpenter's reward is the remainder of the money received from the lord minus the pillar price and transportation costs. As shown in the map below, there are many highways that pass through various towns to reach the mountain village, and the highways that connect the two towns have different transportation costs. How do you follow the road and procure to maximize the carpenter's reward? Create a program that outputs the maximum carpenter's reward. However, if the number of towns is n, then each town is identified by an integer from 1 to n. There are no more than one road that connects the two towns directly.

<image>

* The numbers on the arrows indicate the transportation costs to go in that direction.



Input

The input is given in the following format:


n
m
a1, b1, c1, d1
a2, b2, c2, d2
::
am, bm, cm, dm
s, g, V, P


The first line gives the total number of towns n (n ≤ 20), and the second line gives the total number of roads m (m ≤ 100). The following m lines are given the i-th road information ai, bi, ci, di (1 ≤ ai, bi ≤ n, 0 ≤ ci, di ≤ 1,000). ai and bi are the numbers of the towns connected to the highway i, ci is the transportation cost from ai to bi, and di is the transportation cost from bi to ai.

On the last line, the number s of the town where the carpenter departs, the number g of the mountain village with the pillar, the money V received by the carpenter from the lord, and the price P of the pillar are given.

Output

Output the carpenter's reward (integer) on one line.

Example

Input

6
8
1,2,2,2
1,3,4,3
1,4,4,2
2,5,3,2
3,4,4,2
3,6,1,2
4,6,1,1
5,6,1,2
2,4,50,30


Output

11

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
n = int(input())
m = int(input())
cost = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, sys.stdin.readline().split(','))
	cost[a - 1][b - 1] = c
	cost[b - 1][a - 1] = d
(s, g, V, P) = map(int, sys.stdin.readline().split(','))
for k in range(n):
	for i in range(n):
		c_ik = cost[i][k]
		for (j, (c_kj, c_ij)) in enumerate(zip(cost[k], cost[i])):
			temp = c_ik + c_kj
			if c_ij > temp:
				cost[i][j] = temp
print(V - P - cost[s - 1][g - 1] - cost[g - 1][s - 1])


from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n = int(input())
m = int(input())
edges = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	(a, b) = (a - 1, b - 1)
	edges[a].append((b, c))
	edges[b].append((a, d))
(s, g, v, p) = map(int, input().split(','))
(s, g) = (s - 1, g - 1)

def dij(s, g):
	que = [(0, s)]
	costs = [INF for _ in range(n)]
	costs[s] = 0
	while que:
		(cost, num) = pop(que)
		if num == g:
			return cost
		for edge in edges[num]:
			(to, fee) = edge
			if costs[to] > cost + fee:
				costs[to] = cost + fee
				push(que, (cost + fee, to))
print(v - p - dij(s, g) - dij(g, s))


n = int(input())
m = int(input())
inf = 1001001001
route = [[inf for _ in range(n)] for __ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	route[a - 1][b - 1] = c
	route[b - 1][a - 1] = d
(s, g, V, P) = map(int, input().split(','))
for k in range(n):
	for i in range(n):
		for j in range(n):
			if route[i][j] > route[i][k] + route[k][j]:
				route[i][j] = route[i][k] + route[k][j]
print(int(V - P - route[s - 1][g - 1] - route[g - 1][s - 1]))


INF = 2147483647
import heapq

def dijkstra(V, to, start, goal):
	dist = [INF] * V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while len(Q):
		(t, s) = heapq.heappop(Q)
		if s == goal:
			break
		if dist[s] < t:
			continue
		for i in to[s]:
			(e, cost) = i
			nt = t + cost
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
	return dist[goal]
n = int(input()) + 1
to = [[] for i in range(n)]
for i in range(int(input())):
	(a, b, c, d) = list(map(int, input().split(',')))
	to[a].append((b, c))
	to[b].append((a, d))
(s, g, V, P) = list(map(int, input().split(',')))
if s == g:
	print(V - P)
else:
	print(V - P - dijkstra(n, to, s, g) - dijkstra(n, to, g, s))


N = int(input().strip())
M = int(input().strip())
Inf = 1001001001
K = [[Inf for j in range(N)] for i in range(N)]
for _ in range(M):
	(a, b, c, d) = map(int, input().strip().split(','))
	K[a - 1][b - 1] = c
	K[b - 1][a - 1] = d
(S, G, V, P) = map(int, input().strip().split(','))
for k in range(N):
	for i in range(N):
		for j in range(N):
			if K[i][j] > K[i][k] + K[k][j]:
				K[i][j] = K[i][k] + K[k][j]
R = V - P - K[S - 1][G - 1] - K[G - 1][S - 1]
print(R)


n = int(input())
m = int(input())
Map = [[1001] * n for _ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	Map[a - 1][b - 1] = c
	Map[b - 1][a - 1] = d
(s, g, V, P) = map(int, input().split(','))
for k in range(n):
	for i in range(n):
		for j in range(n):
			if Map[i][j] > Map[i][k] + Map[k][j]:
				Map[i][j] = Map[i][k] + Map[k][j]
print(V - P - Map[s - 1][g - 1] - Map[g - 1][s - 1])


n = int(input())
cost = [[float('inf')] * n for _ in range(n)]
m = int(input())
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	cost[a - 1][b - 1] = c
	cost[b - 1][a - 1] = d
(s, g, V, P) = map(int, input().split(','))
for k in range(n):
	for i in range(n):
		for j in range(n):
			if cost[i][j] > cost[i][k] + cost[k][j]:
				cost[i][j] = cost[i][k] + cost[k][j]
print(V - P - cost[s - 1][g - 1] - cost[g - 1][s - 1])


n = int(input())
m = int(input())
dp = [[float('inf') for _ in range(n)] for _ in range(n)]
for i in range(n):
	dp[i][i] = 0
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	dp[a - 1][b - 1] = c
	dp[b - 1][a - 1] = d
for k in range(n):
	for i in range(n):
		for j in range(n):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
(s, g, v, p) = map(int, input().split(','))
print(v - p - dp[s - 1][g - 1] - dp[g - 1][s - 1])


import math
V = int(input())
E = int(input())
fees = [[math.inf] * V for i in range(V)]
for i in range(V):
	fees[i][i] = 0
for i in range(E):
	(a, b, c, d) = map(int, input().split(','))
	fees[a - 1][b - 1] = c
	fees[b - 1][a - 1] = d
(start, end, funding, cost) = map(int, input().split(','))
for i in range(V):
	for j in range(V):
		for k in range(V):
			if fees[j][k] > fees[j][i] + fees[i][k]:
				fees[j][k] = fees[j][i] + fees[i][k]
if fees[start - 1][end - 1] == math.inf or fees[end - 1][start - 1] == math.inf:
	print(0)
else:
	print(funding - cost - fees[start - 1][end - 1] - fees[end - 1][start - 1])


import sys
from sys import stdin
input = stdin.readline

def warshallFloyd(V, dp):
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if dp[i][k] + dp[k][j] < dp[i][j]:
					dp[i][j] = dp[i][k] + dp[k][j]

def main(args):
	n = int(input())
	m = int(input())
	dp = [[float('inf')] * n for _ in range(n)]
	for i in range(n):
		dp[i][i] = 0
	for _ in range(m):
		(a, b, c, d) = [int(x) for x in input().split(',')]
		dp[a - 1][b - 1] = c
		dp[b - 1][a - 1] = d
	(s, g, V, P) = [int(x) for x in input().split(',')]
	warshallFloyd(n, dp)
	print(V - dp[s - 1][g - 1] - dp[g - 1][s - 1] - P)
main(sys.argv[1:])


from heapq import heappush, heappop

def solve():
	N = int(input())
	M = int(input())
	G = [[] for i in range(N)]
	for i in range(M):
		(a, b, c, d) = map(int, input().split(','))
		G[a - 1].append((b - 1, c))
		G[b - 1].append((a - 1, d))
	(s, g, V, P) = map(int, input().split(','))
	INF = 10 ** 18

	def calc(s, g):
		dist = [INF] * N
		dist[s] = 0
		que = [(0, s)]
		while que:
			(cost, v) = heappop(que)
			if dist[v] < cost:
				continue
			for (w, d) in G[v]:
				if cost + d < dist[w]:
					dist[w] = cost + d
					heappush(que, (cost + d, w))
		return dist[g]
	s -= 1
	g -= 1
	print(max(0, V - (calc(s, g) + calc(g, s)) - P))
solve()


INF = 1000000

def bellman_ford(graph, source):
	lg = len(graph)
	unused = list(range(lg))
	d = [INF] * lg
	d[source] = 0
	while unused:
		v = min(unused, key=lambda u: d[u])
		unused.remove(v)
		for u in range(n + 1):
			d[u] = min(d[u], d[v] + graph[v][u])
	return d
n = int(input())
m = int(input())
cost = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(ai, bi, ci, di) = map(int, input().split(','))
	cost[ai][bi] = ci
	cost[bi][ai] = di
(x1, x2, y1, y2) = map(int, input().split(','))
d_go = bellman_ford(cost, x1)[x2]
d_back = bellman_ford(cost, x2)[x1]
print(y1 - y2 - d_go - d_back)


n = int(input())
m = int(input())
inf = 1001001001
data = [[inf] * n for i in range(n)]
for i in range(m):
	(a, b, c, d) = map(int, input().split(','))
	data[a - 1][b - 1] = c
	data[b - 1][a - 1] = d
(s, g, V, P) = map(int, input().split(','))
for k in range(n):
	for i in range(n):
		for j in range(n):
			if data[i][j] > data[i][k] + data[k][j]:
				data[i][j] = data[i][k] + data[k][j]
print(V - P - data[s - 1][g - 1] - data[g - 1][s - 1])


n = int(input())
m = int(input())
cost = []
for i in range(n):
	t = [float('inf')] * n
	t[i] = 0
	cost.append(t)
for i in range(m):
	s = input()
	s += ','
	L = []
	z = ''
	for j in range(len(s)):
		if s[j] != ',':
			z += s[j]
		else:
			L.append(int(z))
			z = ''
	(a, b, c, d) = (L[0], L[1], L[2], L[3])
	cost[a - 1][b - 1] = c
	cost[b - 1][a - 1] = d
for k in range(n):
	for i in range(n):
		for j in range(n):
			if cost[i][j] > cost[i][k] + cost[k][j]:
				cost[i][j] = cost[i][k] + cost[k][j]
s = input()
s += ','
L = []
z = ''
for j in range(len(s)):
	if s[j] != ',':
		z += s[j]
	else:
		L.append(int(z))
		z = ''
(s, g, v, p) = (L[0], L[1], L[2], L[3])
print(v - p - cost[s - 1][g - 1] - cost[g - 1][s - 1])


n = int(input())
m = int(input())
l = []
for i in range(m):
	l1 = list(map(int, input().split(',')))
	l.append(l1)
(s, g, v, p) = map(int, input().split(','))
listl = [[100000 for i in range(n + 1)] for i in range(n + 1)]
for i in l:
	listl[i[0]][i[1]] = i[2]
	listl[i[1]][i[0]] = i[3]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			if listl[j][k] > listl[j][i] + listl[i][k]:
				listl[j][k] = listl[j][i] + listl[i][k]
print(v - p - (listl[s][g] + listl[g][s]))


n = int(input())
m = int(input())
K = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b, c, d) = map(int, input().split(','))
	K[a - 1][b - 1] = c
	K[b - 1][a - 1] = d
for k in range(n):
	for i in range(n):
		for j in range(n):
			if K[i][j] > K[i][k] + K[k][j]:
				K[i][j] = K[i][k] + K[k][j]
(s, g, V, P) = map(int, input().split(','))
print(V - P - K[s - 1][g - 1] - K[g - 1][s - 1])


n = int(input())
m = int(input())
roads = [[float('inf') for _ in range(n)] for _ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	roads[a - 1][b - 1] = c
	roads[b - 1][a - 1] = d
(s, g, V, P) = map(int, input().split(','))
for k in range(n):
	for i in range(n):
		for j in range(n):
			if roads[i][j] > roads[i][k] + roads[k][j]:
				roads[i][j] = roads[i][k] + roads[k][j]
print(V - P - roads[s - 1][g - 1] - roads[g - 1][s - 1])


n = int(input())
m = int(input())
mat = [[float('inf')] * n for _ in [0] * n]
for (a, b, c, d) in (map(int, input().split(',')) for _ in [0] * m):
	mat[a - 1][b - 1] = c
	mat[b - 1][a - 1] = d
(s, g, v, p) = map(int, input().split(','))
for k in range(n):
	for i in range(n):
		for j in range(n):
			mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
print(v - p - mat[s - 1][g - 1] - mat[g - 1][s - 1])


from heapq import heappop, heappush

def solve(graph, start, goal, numnodes):
	que = []
	heappush(que, (0, start - 1))
	mindists = [float('inf')] * numnodes
	while que:
		(ccost, cnode) = heappop(que)
		if mindists[cnode] < ccost:
			continue
		for (nnode, mcost) in graph[cnode]:
			tcost = ccost + mcost
			if mindists[nnode] > tcost:
				mindists[nnode] = tcost
				heappush(que, (tcost, nnode))
	return mindists[goal - 1]
n = int(input())
m = int(input())
graph = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	graph[a - 1].append((b - 1, c))
	graph[b - 1].append((a - 1, d))
(s, g, V, P) = map(int, input().split(','))
V -= solve(graph, s, g, n)
V -= P
V -= solve(graph, g, s, n)
print(V)


import sys
from sys import stdin
input = stdin.readline

def warshallFloyd(V, dp):
	for k in range(V):
		for i in range(V):
			for j in range(V):
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

def main(args):
	n = int(input())
	m = int(input())
	dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
	for i in range(n + 1):
		dp[i][i] = 0
	for _ in range(m):
		(a, b, c, d) = [int(x) for x in input().split(',')]
		dp[a][b] = c
		dp[b][a] = d
	(s, g, V, P) = [int(x) for x in input().split(',')]
	warshallFloyd(n + 1, dp)
	print(V - dp[s][g] - dp[g][s] - P)
main(sys.argv[1:])


inf = 200000
n = int(input())
m = int(input())
adj = [[inf] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(a, b, c, d) = map(int, input().split(sep=','))
	adj[a][b] = c
	adj[b][a] = d
(s, g, v, p) = map(int, input().split(sep=','))
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
ans = v - p
ans -= adj[s][g]
ans -= adj[g][s]
print(ans)


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
	N = int(input())
	M = int(input())
	dist = [[INF] * N for _ in range(N)]
	for _ in range(M):
		(a, b, c, d) = map(int, input().split(','))
		a -= 1
		b -= 1
		dist[a][b] = c
		dist[b][a] = d
	(s, g, v, p) = map(int, input().split(','))
	for k in range(N):
		for i in range(N):
			for j in range(N):
				dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])
	s -= 1
	g -= 1
	ans = v - dist[s][g] - dist[g][s] - p
	print(ans)
main()


class Graph:
	from collections import namedtuple
	__Pair = namedtuple('Pair', 'cost point')

	def __init__(self, townCount):
		self.__townCount = townCount
		self.__adjacencyList = [[] for _ in range(townCount)]

	def GetPath(self, beginPoint, endPoint, cost):
		item = self.__Pair(cost, endPoint)
		self.__adjacencyList[beginPoint].append(item)

	def Dijkstra(self, beginPoint):
		from sys import maxsize as MaxValue
		from queue import PriorityQueue
		stateTable = {'NotVisited': 0, 'Stay': 1, 'Visited': 2}
		pq = PriorityQueue()
		costTable = [MaxValue for _ in range(self.__townCount)]
		visitState = [stateTable['NotVisited'] for _ in range(self.__townCount)]
		costTable[beginPoint] = 0
		pq.put_nowait(self.__Pair(0, beginPoint))
		while not pq.empty():
			minItem = pq.get_nowait()
			(minPoint, minCost) = (minItem.point, minItem.cost)
			visitState[minPoint] = stateTable['Visited']
			if minCost <= costTable[minPoint]:
				for (cost, point) in self.__adjacencyList[minPoint]:
					if visitState[point] != stateTable['Visited']:
						if costTable[minPoint] + cost < costTable[point]:
							costTable[point] = costTable[minPoint] + cost
							visitState[point] = stateTable['Stay']
							pq.put_nowait(self.__Pair(costTable[point], point))
		return costTable
townCount = int(input())
wayCount = int(input())
graph = Graph(townCount)
for lp in range(wayCount):
	(begin, end, cost1, cost2) = [int(item) for item in input().split(',')]
	begin -= 1
	end -= 1
	graph.GetPath(begin, end, cost1)
	graph.GetPath(end, begin, cost2)
(beginPoint, endPoint, budget, pillarCost) = [int(item) for item in input().split(',')]
beginPoint -= 1
endPoint -= 1
leaveCost = graph.Dijkstra(beginPoint)
returnCost = graph.Dijkstra(endPoint)
result = budget - pillarCost - leaveCost[endPoint] - returnCost[beginPoint]
print(result)


INF = 10000000
n = int(input())
m = int(input())
table = [[INF for i in range(n)] for j in range(n)]
for l in range(m):
	(a, b, c, d) = [int(i) for i in input().split(',')]
	table[a - 1][b - 1] = c
	table[b - 1][a - 1] = d
(s, g, V, P) = [int(i) for i in input().split(',')]
visited = [False for i in range(n)]
cost = [INF for i in range(n)]
cost[s - 1] = 0
while True:
	v = -1
	for i in range(n):
		if visited[i] == False and (v == -1 or cost[i] < cost[v]):
			v = i
	if v == -1:
		break
	visited[v] = True
	for i in range(n):
		cost[i] = min(cost[i], cost[v] + table[v][i])
ans = cost[g - 1]
visited = [False for i in range(n)]
cost = [INF for i in range(n)]
cost[g - 1] = 0
while True:
	v = -1
	for i in range(n):
		if visited[i] == False and (v == -1 or cost[i] < cost[v]):
			v = i
	if v == -1:
		break
	visited[v] = True
	for i in range(n):
		cost[i] = min(cost[i], cost[v] + table[v][i])
ans += cost[s - 1]
print(V - P - ans)


V = int(input())
E = int(input())
dist = [[float('inf')] * V for _ in range(V)]
for i in range(V):
	dist[i][i] = 0
for _ in range(E):
	(a, b, c, d) = map(int, input().split(','))
	(dist[a - 1][b - 1], dist[b - 1][a - 1]) = (c, d)
(fr, to, money, cost) = map(int, input().split(','))
for k in range(V):
	for i in range(V):
		for j in range(V):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
print(money - cost - dist[fr - 1][to - 1] - dist[to - 1][fr - 1])


from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n = int(input())
m = int(input())
edges = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c, d) = map(int, input().split(','))
	(a, b) = (a - 1, b - 1)
	edges[a].append((b, c))
	edges[b].append((a, d))
(s, g, v, p) = map(int, input().split(','))
(s, g) = (s - 1, g - 1)

def dij(s, g):
	que = [(0, s)]
	costs = [INF for _ in range(n)]
	costs[s] = 0
	while que:
		(cost, num) = pop(que)
		if num == g:
			return cost
		for edge in edges[num]:
			(to, fee) = edge
			if costs[to] > cost + fee:
				costs[to] = cost + fee
				push(que, (cost + fee, to))
print(v - p - dij(s, g) - dij(g, s))


INF = 1000000000000.0

def dijkstra(graph, source):
	lg = len(graph)
	unused = list(range(lg))
	d = [INF] * lg
	d[source] = 0
	while unused:
		v = min(unused, key=lambda u: d[u])
		unused.remove(v)
		for u in range(n + 1):
			d[u] = min(d[u], d[v] + graph[v][u])
	return d
n = int(input())
m = int(input())
cost = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(ai, bi, ci, di) = map(int, input().split(','))
	cost[ai][bi] = ci
	cost[bi][ai] = di
(x1, x2, y1, y2) = map(int, input().split(','))
d_go = dijkstra(cost, x1)[x2]
d_back = dijkstra(cost, x2)[x1]
print(y1 - y2 - d_go - d_back)


town_num = int(input())
road_num = int(input())
costs = [[100000] * town_num for _ in range(town_num)]
for (a, b, c, d) in [list(map(int, input().split(','))) for _ in range(road_num)]:
	costs[a - 1][b - 1] = c
	costs[b - 1][a - 1] = d
(s, g, v, p) = map(int, input().split(','))
for k in range(town_num):
	for i in range(town_num):
		for j in range(town_num):
			if costs[i][j] > costs[i][k] + costs[k][j]:
				costs[i][j] = costs[i][k] + costs[k][j]
print(v - p - costs[s - 1][g - 1] - costs[g - 1][s - 1])


INF = 1000000
n = int(input())
m = int(input())
cost = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(ai, bi, ci, di) = (int(s) for s in input().split(','))
	cost[ai][bi] = ci
	cost[bi][ai] = di
(x1, x2, y1, y2) = (int(s) for s in input().split(','))
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if cost[i][j] > cost[i][k] + cost[k][j]:
				cost[i][j] = cost[i][k] + cost[k][j]
print(y1 - y2 - cost[x1][x2] - cost[x2][x1])


import sys
import os
from collections import defaultdict
n = int(input())
m = int(input())
M = defaultdict(list)
for i in range(m):
	(a, b, c, d) = list(map(int, input().split(',')))
	a -= 1
	b -= 1
	M[a].append((b, c))
	M[b].append((a, d))
(s, g, V, P) = list(map(int, input().split(',')))
s -= 1
g -= 1

def min_dist(Q, dists):
	min_v = float('inf')
	min_i = None
	for i in Q:
		if dists[i] < min_v:
			min_v = dists[i]
			min_i = i
	return (min_v, min_i)

def dijkstra(i, j, M):
	n = len(M)
	dists = [float('inf')] * n
	dists[i] = 0
	Q = [i for i in range(n)]
	while Q:
		min_dist_index = min_dist(Q, dists)[1]
		Q.remove(min_dist_index)
		for (idx, cost) in M[min_dist_index]:
			if dists[idx] > dists[min_dist_index] + cost:
				dists[idx] = dists[min_dist_index] + cost
	return dists[j]
res0 = dijkstra(s, g, M)
res1 = dijkstra(g, s, M)
print(V - P - res0 - res1)


n = int(input())
m = int(input())
K = [[10 ** 9 for one in range(32)] for two in range(32)]
for three in range(m):
	(a, b, c, d) = map(int, input().split(','))
	K[a][b] = c
	K[b][a] = d
for k in range(1, n + 1):
	for j in range(1, n + 1):
		for i in range(1, n + 1):
			if K[i][j] > K[i][k] + K[k][j]:
				K[i][j] = K[i][k] + K[k][j]
(s, g, V, P) = map(int, input().split(','))
print(V - P - K[s][g] - K[g][s])


import sys, math, os
PYDEV = os.environ.get('PYDEV')
if PYDEV == 'True':
	sys.stdin = open('sample-input.txt', 'rt')

class DirectedGraph:

	def __init__(self):
		self.neighbor_dict = {}
		self.explored_dict = {}

	def HasNode(self, node):
		return node in self.neighbor_dict

	def AddNode(self, node):
		if self.HasNode(node):
			return
		self.neighbor_dict[node] = []
		self.explored_dict[node] = False

	def AddEdge(self, node1, node2, length):
		if not self.HasNode(node1):
			self.AddNode(node1)
		if not self.HasNode(node2):
			self.AddNode(node2)
		neighbors = self.neighbor_dict[node1]
		neighbors.append((node2, length))
		self.neighbor_dict[node1] = neighbors

	def GetExplored(self, node):
		return self.explored_dict[node]

	def GetNextUnexploredNeighbor(self, node):
		for neighbor in self.GetNeighbors(node):
			if not self.GetExplored(neighbor):
				return neighbor
		return -1

	def SetExplored(self, node, value):
		self.explored_dict[node] = value

	def GetNodes(self):
		return self.neighbor_dict.keys()

	def GetNeighbors(self, node):
		result = []
		for neighbor in self.neighbor_dict[node]:
			result.append(neighbor[0])
		return result

	def GetEdgeLength(self, node1, node2):
		result = 9999999999999999
		neighbors = self.neighbor_dict[node1]
		for neighbor in neighbors:
			if neighbor[0] == node2:
				return neighbor[1]
		return result

	def GetNumExploredNodes(self):
		num = 0
		for (key, value) in self.explored_dict.items():
			if value:
				num += 1
		return num

	def GetDegree(self, node):
		return len(self.GetNeighbors(node))

	def GetOrderedDegrees(self):
		result = []
		nodes = self.GetNodes()
		for node in nodes:
			result.append((node, self.GetDegree(node)))
		return sorted(result, key=lambda result: result[1], reverse=True)

	def GetAllEdges(self):
		result = []
		nodes = self.GetNodes()
		for node in nodes:
			neighbors = self.GetNeighbors(node)
			for neighbor in neighbors:
				result.append((node, neighbor))
		return result

def dijkstra(graph, s):
	n = len(graph.GetNodes())
	X = [s]
	A = {}
	A[s] = 0
	while len(A) < n:
		dijkstra_greedy = 999999999999999999999
		v_star = -1
		w_star = -1
		for v in X:
			for w in graph.GetNeighbors(v):
				if w not in X:
					current_dist = A[v] + graph.GetEdgeLength(v, w)
					if current_dist < dijkstra_greedy:
						v_star = v
						w_star = w
						dijkstra_greedy = current_dist
		X.append(w_star)
		A[w_star] = dijkstra_greedy
	for node in graph.GetNodes():
		if node not in A.keys():
			A[node] = 1000000
	return A
G = DirectedGraph()
n = int(input())
for city in range(1, n + 1):
	G.AddNode(city)
m = int(input())
for road in range(m):
	(city1, city2, cost1, cost2) = [int(_) for _ in input().split(',')]
	G.AddEdge(city1, city2, cost1)
	G.AddEdge(city2, city1, cost2)
(source, target, money, price) = [int(_) for _ in input().split(',')]
d = dijkstra(G, source)
cost1 = d[target]
d = dijkstra(G, target)
cost2 = d[source]
print(money - price - cost1 - cost2)