#include using namespace std; const int INF = 300000000; int main(){ int N, M; cin >> N >> M; vector> E(N); for (int i = 0; i < M; i++){ int U, V; cin >> U >> V; U--; V--; E[U].push_back(V); E[V].push_back(U); } vector A(N), B(N), C(N); for (int i = 0; i < N; i++){ cin >> A[i] >> B[i] >> C[i]; } int mn = INF; for (int v : E[0]){ mn = min(mn, A[v] + B[v] + C[v]); } int tv = 300000000, fv = A[0] + B[0] + C[0] - 2; while (tv - fv > 1){ int mid = (tv + fv) / 2; int a = mid, b = 1, c = 1; if (mid - 1 + max({A[0], B[0], C[0]}) < mn){ fv = mid; } else { vector used(N, false); priority_queue, vector>, greater>> pq; pq.push(make_pair(A[0] + B[0] + C[0], 0)); while (!pq.empty()){ int sum = pq.top().first; int v = pq.top().second; pq.pop(); if (!used[v] && sum < a + b + c){ used[v] = true; vector tmp = {a, b, c, A[v], B[v], C[v]}; sort(tmp.begin(), tmp.end(), greater()); a = tmp[0]; b = tmp[1]; c = tmp[2]; for (int w : E[v]){ if (!used[w]){ pq.push(make_pair(A[w] + B[w] + C[w], w)); } } } } if (used[N - 1]){ tv = mid; } else { fv = mid; } } } cout << tv << ' ' << 1 << ' ' << 1 << endl; }