// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 3e5 + 10;
int n, m, f[N], id, a[N], b[N];
ll mx = -1e18, mx2 = -1e18, t[N][3];//, ans[N];
vector <int> v[N];//, vv[N];
bool vis[N][2];
signed main() {
	read(n), read(m);
	F(i, 1, n) read(a[i]), read(b[i]);
	F(i, 1, m) {
		int x, y; read(x), read(y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	{
		queue <int> q; q.push(1);
		ms(f, 0x3f); f[1] = 0;
		ms(t, 0x9f);
		while (q.size()) {
			int x = q.front(); q.pop();
			for (int i: v[x])
				if (f[x] + 1 < f[i]) {
					f[i] = f[x] + 1;
					q.push(i);
				}
		}
	}
	{
		// priority_queue <pair <ll, pair <int, int>>, vector <pair <ll, pair <int, int>>>, greater <pair <ll, pair <int, int>>>> q;
		priority_queue <pair <ll, pair <int, int>>> q;
		ms(t, 0x9f);
		F(i, 1, n) {
			ll x = a[i] - (ll) b[i] * (f[i] + 1);
			if (x > mx) mx2 = mx, mx = x, id = i;
			else chkmax(mx2, x);
			t[i][0] = a[i] - (ll) b[i] * (f[i] - 1);
			// if (i == 5) debug << t[i][0] << " " << f[i] << endl;
			t[i][1] = a[i] - (ll) b[i] * f[i];
			q.emplace(t[i][0], make_pair(i, 0));
			q.emplace(t[i][1], make_pair(i, 1));
		}
		while (q.size()) {
			int x = q.top().second.first, y = q.top().second.second; q.pop();
			if (vis[x][y]) continue;
			for (int i: v[x]) {
				if (f[x] == f[i] + 1) {
					if (t[x][y] > t[i][y]) q.emplace(t[i][y] = t[x][y], make_pair(i, y));
				} else if (f[i] == f[x]) {
					if (y == 1 && t[x][y] > t[i][2]) q.emplace(t[i][2] = t[x][y], make_pair(i, 2));
				}
			}
		}
		sort(all(v[1]));
		for (int i: v[1]) {
			ll ans = (id == i ? mx2 : mx);
			for (int j: v[i]) {
				// if (i == 4 && j == 5) {
				// 	debug << t[j][0] << " " << t[j][2] << endl;
				// }
				if (f[j] == f[i] + 1) chkmax(ans, t[j][0]), chkmax(ans, t[j][2]);
				else if (f[j] == f[i]) chkmax(ans, t[j][1]);
			}
			cout << ans << '\n';
		}
	}
	return 0;
}
/* why?
*/