mod = 998244353 def main(): import sys from heapq import heappop, heappush input = sys.stdin.readline def trade(X, Y): Z = sorted(X + Y, reverse=True) return Z[:3] N, M = map(int, input().split()) adj = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, input().split()) adj[a].append(b) adj[b].append(a) ABC = [[0, 0, 0]] * (N + 1) for v in range(1, N+1): ABC[v] = list(map(int, input().split())) ABC_sum = [sum(abc) for abc in ABC] ans = 3 * 10 ** 8 ans_k = -1 for k in range(1): ok = 3 * 10 ** 8 ng = 1 mid = (ok + ng) // 2 while ok - ng > 1: X = [1] * 3 X[k] = mid # 頂点1で勝てるかどうか if sum(X) <= sum(ABC[1]): ng = mid mid = (ok + ng) // 2 continue else: diff_max = -10 ** 8 diff_max_idx = -1 for i in range(3): d = ABC[1][i] - X[i] if d > diff_max: diff_max = d diff_max_idx = i if X[diff_max_idx] < ABC[1][diff_max_idx]: X[diff_max_idx] = ABC[1][diff_max_idx] S = sum(X) flg = 0 for u in adj[1]: if S > ABC_sum[u]: flg = 1 break if not flg: ng = mid continue X = trade(X, ABC[1]) seen = [0] * (N + 1) pq = [(0, 1)] seen[1] = 1 flg = 1 while pq: s, v = heappop(pq) if s >= sum(X): flg = 0 break else: if v == N: break X = trade(X, ABC[v]) for u in adj[v]: if not seen[u]: heappush(pq, (ABC_sum[u], u)) seen[u] = 1 if flg: ok = mid else: ng = mid mid = (ok + ng) // 2 if ok + 2 < ans: ans = ok + 2 ans_k = k ANS = [1] * 3 ANS[ans_k] = ans - 2 print(*ANS) if __name__ == '__main__': main()