#include using i64 = long long; int main() { int n, m; scanf("%d%d", &n, &m); std::vector u(m), v(m), a(n), b(n), c(n); std::vector> g(n); for(int i = 0; i < m; i++) { scanf("%d%d", &u[i], &v[i]); u[i]--; v[i]--; g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } for(int i = 0; i < n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]); if(n == 1) { // no case exist } std::vector d(n); for(int i = 0; i < n; i++) d[i] = a[i] + b[i] + c[i]; for(int i = 0; i < n; i++) { int min = std::min({a[i], b[i], c[i]}); int max = std::max({a[i], b[i], c[i]}); a[i] = min; b[i] = d[i] - min - max; c[i] = max; } int A = 1, B = 1, C = d[0] - 1, ans = d[0] - 1; // A <= B <= C auto update = [&](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; } }; update(c[0]); { int v = 0; for(int to: g[0]) if(d[v] > d[to]) v = to; if(A + B + C <= d[v]) { // 足りていない ans = C = d[v] - A - B + 1; } } using P = std::pair; std::priority_queue, std::greater<>> qu; qu.push({d[0], 0}); std::vector used(n); used[0] = true; while(!qu.empty()) { auto [sum, v] = qu.top(); qu.pop(); if(sum >= A + B + C) { // 足りていない int diff = sum - A - B - C + 1; if(ans == A) { A += diff; ans += diff; } else if(ans == B) { B += diff; ans += diff; } else if(ans == C) { C += diff; ans += diff; } else { A += diff; ans = A; } } if(v == n - 1) { printf("1 1 %d\n", ans); break; } update(a[v]); update(b[v]); update(c[v]); for(int to: g[v]) { if(used[to]) continue; used[to] = true; qu.push({d[to], to}); } } return 0; }