import heapq def solve(n, m, graph, abc): for i in range(n): abc[i].sort(reverse=True) def check(x): # A = x, B = 1, C = 1で突破できる? myabc = [x, 1, 1] q = [] good = [False] * n visit = [False] * n if sum(abc[0]) >= sum(myabc): return False myabc[1] = abc[0][0] good[0] = True visit[0] = True for to in graph[0]: visit[to] = True heapq.heappush(q, (sum(abc[to]), to)) while q: nowsum, now = heapq.heappop(q) if nowsum < sum(myabc): good[now] = True if now == n - 1: return True else: return False myabc.sort(reverse=True) myabc[1] = max(myabc[1], abc[0][1]) myabc[2] = max(myabc[2], abc[0][0]) myabc[1] = max(myabc[1], abc[now][1]) myabc[2] = max(myabc[2], abc[now][0]) for to in graph[now]: if not visit[to]: visit[to] = True heapq.heappush(q, (sum(abc[to]), to)) return good[n - 1] ok, ng = 3 * 10 ** 8, 1 while abs(ok - ng) > 1: mid = (ok + ng) // 2 if check(mid): ok = mid else: ng = mid return ok, 1, 1 n, m = map(int, input().split()) graph = [[] for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 graph[u].append(v) graph[v].append(u) abc = [list(map(int, input().split())) for _ in range(n)] a, b, c = solve(n, m, graph, abc) print(a, b, c)