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 X_ori = X[:] # 頂点1で勝てるかどうか if sum(X) <= sum(ABC[1]): ng = mid mid = (ok + ng) // 2 continue else: ma_1 = max(ABC[1]) X[1] = max(X[1], ma_1) S = sum(X) flg = 0 for u in adj[1]: if S > ABC_sum[u]: flg = 1 break if not flg: ng = mid mid = (ok + ng) // 2 continue X = trade(X_ori, 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 ans_k = k ANS = [1] * 3 ANS[ans_k] = ans print(*ANS) if __name__ == '__main__': main()