# include <iostream>
# include <cstdio>
# include <queue>
# include <cstring>
using namespace std;
# define int long long
const int maxn = 500 + 5;
const int maxm = 4000 + 5;
const int maxe = 2e6 + 5; 
const int inf = 1e18;
int dist[maxn][maxn];

int n , m;
int cow[maxn] , canopy[maxn];
int sum;
int x , y ,z;
int S , T;
int cur[maxm];
typedef struct {
	int x , y , z , next;
}Edge;
Edge edge[maxe];
int E = 1 , elast[maxm];
void add(int x , int y , int z) {
	E ++;
	edge[E].x = x;
	edge[E].y = y;
	edge[E].z = z;
	edge[E].next = elast[x];
	elast[x] = E;
}
int dis[maxm] , cnt[maxm];
void bfs(int start) {
	queue<int> q;
	dis[start] = 0;	
	q.push(start);
	cnt[S] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = elast[cur] ; i ; i = edge[i].next) {
			int v = edge[i].y;
			if (dis[v]) continue;
			q.push(v);
			dis[v] = dis[cur] + 1;
			cnt[dis[v]] ++;
		}
	}
}
int dfs(int u , int flow) {
	if (u == T) return flow;
	int temp , delta = 0;
	for (int i = cur[u] ; i ; i = edge[i].next) {
		cur[u] = i;
		int v = edge[i].y;
		if (edge[i].z > 0 && dis[u] == dis[v] + 1) {
			temp = dfs(v , min(flow - delta , edge[i].z));
			edge[i].z -= temp;
			edge[i ^ 1].z += temp;
			delta += temp;
			if (delta == flow) return delta;
		}
	}
	if (dis[S] >= T) return delta; 
	cur[u] = elast[u];
	if (-- cnt[dis[u]] == 0) dis[S] = T;
	cnt[++ dis[u]] ++;
	return delta;
}
int Isap() {
	int Ans = 0;
	memset(dis , 0 , sizeof dis);
	memset(cnt , 0 , sizeof cnt);
	for (int i = 1 ; i <= T ; i ++) {
		cur[i] = elast[i];
	}
	//bfs(T);
	
	
	while (dis[S] < T) {
		Ans += dfs(S , inf);
	} 
	//cout << Ans << endl; 
	return Ans;
	
}
bool check(int min_time) {
	memset(elast , 0 , sizeof elast);
	E = 1;
	for (int i = 1 ; i <= n ; i ++) {
		add(S , i , cow[i]);
		add(i , S , 0);
		add(i + n , T , canopy[i]);
		add(T , i + n , 0);
		add(i , i + n , inf);
		add(i + n , i , 0);
	}
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = 1 ; j <= n ; j ++) {
			if (dist[i][j] <= min_time) {
				add(i , j + n , inf);
				add(j + n , i , 0);
			} 
		}
	}
	//system("pause");
	/*
    for (int i = 1 ; i <= E ; i ++) {
    	printf("%d %d %d\n" , edge[i].x , edge[i].y , edge[i].z);
	}
	cout << " ak ioi " << endl;
	*/
	if (Isap() == sum) return true;
	else return false;
}

signed main() {
	cin >> n >> m;
	for (int i = 1 ; i <= n ; i ++) {
		scanf("%d%d" , &cow[i] , &canopy[i]);
		sum += cow[i];
	} 
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = 1 ; j <= n ; j ++) {
			dist[i][j] = inf;
		}
	}
	for (int i = 1 ; i <= m ; i ++) {
		scanf("%d%d%d" , &x , &y , &z);
		dist[x][y] = min(dist[x][y] , z);
		dist[y][x] = min(dist[y][x] , z);
	}
	for (int k = 1 ; k <= n ; k ++) {
		for (int i = 1 ; i <= n ; i ++) {
			for (int j = 1 ; j <= n ; j ++) {
				dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
			}
		}
	}
	/*
	int r = 0;
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = 1 ; j <= n ; j ++) {
			r = max(r , dist[i][j]);
		}
	}
	int R = r;
	*/
	S = 0 , T = n << 1 | 1;
	int l = 0 , r = inf;
	int ans = 0;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid) == true) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	if (ans == 0 || ans == inf) puts("-1");
	else printf("%d\n" , ans);
	return 0;
}