import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) N,M = mi() edge = [[] for v in range(N)] for _ in range(M): u,v = mi() edge[u-1].append(v-1) edge[v-1].append(u-1) _card = [] for i in range(N): a,b,c = mi() _card.append(sorted([a,b,c])) mask = 2**20-1 def cond(k): card = [[a for a in _card[v]] for v in range(N)] my_card = [1,1,k-2] if sum(card[0]) >= k: return False if my_card[0] < card[0][2]: my_card[0],card[0][2] = card[0][2],my_card[0] card[0].sort() my_card.sort() pq = [(-card[0][2],0)] visit = [False] * N visit[0] = True f = False for v in edge[0]: if sum(card[v]) < sum(my_card): f = True heappush(pq,(-card[v][2],v)) visit[v] = True if not f: return False strong = [] for v in range(N): if visit[v]: for nv in edge[v]: if not visit[nv]: S = sum(card[nv]) heappush(strong,(S<<20)+nv) while True: #print(visit) #print(card) #print(my_card) #print(pq) change = False new_v = False val,v = heappop(pq) val = -val #print(val,v) i = card[v].index(val) if val > my_card[0]: change = True my_card[0],card[v][i] = card[v][i],my_card[0] card[v].sort() my_card.sort() heappush(pq,(-card[v][2],v)) while strong: V = strong[0] val,nv = V>>20,V&mask if visit[nv]: heappop(strong) continue if val < sum(my_card): new_v = True heappop(strong) visit[nv] = True heappush(pq,(-card[nv][2],nv)) for nnv in edge[nv]: if not visit[nnv]: S = sum(card[nnv]) heappush(strong,(S<<20)+nnv) else: break if not change and not new_v: break return visit[-1] ok = 10**9 ng = 2 while ok-ng>1: mid = (ok+ng)//2 if cond(mid): ok = mid else: ng = mid print(1,1,ok-2)