#include <bits/stdc++.h> using namespace std; const int INF = 300000000; int main(){ int N, M; cin >> N >> M; vector<vector<int>> 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<int> 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 = 0; while (tv - fv > 1){ int mid = (tv + fv) / 2; int a = mid, b = 1, c = 1; if (a + b + c <= A[0] + B[0] + C[0]){ fv = mid; } else if (a + b + c - 1 + max({A[0], B[0], C[0]}) <= mn){ fv = mid; } else { vector<bool> used(N, false); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> 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<int> tmp = {a, b, c, A[v], B[v], C[v]}; sort(tmp.begin(), tmp.end(), greater<int>()); 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; }