import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void upd(int A, int B, int C, int x){ if (C < x){ A = B; B = C; C = x; } else if (B < x){ A = B; B = x; } else if(A < x){ A = x; } return; } public static boolean solve(int n, int m, int minv, int[] a, int[] b, int[] c, int[] d, ArrayList[] graph, int nowc){ int A = 1; int B = 1; int C = nowc; if(d[0] >= A + B + C) return false; int x = c[0]; if (C < x){ A = B; B = C; C = x; } else if (B < x){ A = B; B = x; } else if(A < x){ A = x; } if (d[minv] >= A + B + C) return false; A = 1; B = 1; PriorityQueue Q = new PriorityQueue<>(); Q.add(new Pair(d[0], 0)); boolean[] visit = new boolean[n]; for(int i = 0; i < n; i++){ visit[i] = false; } visit[0] = true; int sum, now; while(Q.size() > 0){ Pair temp = Q.poll(); sum = temp.time; now = temp.ver; if(sum >= A + B + C) return false; if(now == n - 1) return true; x = a[now]; if (C < x){ A = B; B = C; C = x; } else if (B < x){ A = B; B = x; } else if(A < x){ A = x; } x = b[now]; if (C < x){ A = B; B = C; C = x; } else if (B < x){ A = B; B = x; } else if(A < x){ A = x; } x = c[now]; if (C < x){ A = B; B = C; C = x; } else if (B < x){ A = B; B = x; } else if(A < x){ A = x; } for(int to: graph[now]){ if (!visit[to]){ visit[to] = true; Q.add(new Pair(d[to], to)); } } } return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n, m; n = sc.nextInt(); m = sc.nextInt(); int[] a = new int[n]; int[] b = new int[n]; int[] c = new int[n]; ArrayList[] graph = new ArrayList[n]; for(int i = 0; i < n; i++){ graph[i] = new ArrayList(); } int u, v; for(int i = 0; i < m ;i++){ u = sc.nextInt(); v = sc.nextInt(); u--; v--; graph[u].add(v); graph[v].add(u); } for(int i = 0; i < n; i++){ a[i] = sc.nextInt(); b[i] = sc.nextInt(); c[i] = sc.nextInt(); } int[] d = new int[n]; for(int i = 0; i < n; i++){ d[i] = a[i] + b[i] + c[i]; } int min , max; for(int i = 0; i < n; i++){ min = Math.min(Math.min(a[i], b[i]), c[i]); max = Math.max(Math.max(a[i], b[i]), c[i]); a[i] = min; b[i] = d[i] - min - max; c[i] = max; } int mint = graph[0].get(0); for(int to: graph[0]){ if(d[to] < d[mint]) mint = to; } int ok = 1000000000; int ng = 1; int mid; while(Math.abs(ok - ng) > 1){ mid = (ok + ng) / 2; if(solve(n, m, mint, a, b, c, d, graph, mid)){ ok = mid; } else ng = mid; } System.out.printf("%d %d %d\n", ok, 1, 1); } } class Pair implements Comparable{ int time; int ver; public Pair(int time, int ver) { this.time = time; this.ver = ver; } @Override public int compareTo(Pair p) { return Integer.compare(time, p.time); } }