#include "bits/stdc++.h"
using namespace std;
struct Edge {
	int src;
	int dst;
	long long int cost;
	int type;
};
struct aa {
	int upnext;
	int downnext;
	long long int time;
};

class Compare {
public:
	//aa?????????????????¶
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};
int main() {
	while (1) {
		int N, M; cin >> N >> M;
		if (!N)break;
		vector<int>hs(N), moneys(N);
		hs[0] = 0;
		map<int, vector<int>>mp;
		mp[0].push_back(0);
		for (int i = 1; i < N - 1; ++i) {
			cin >>moneys[i] >> hs[i];
			mp[hs[i]].push_back(i);
		}
		mp[1000].push_back(N - 1);
		hs[N - 1] = 1000;
		vector<vector<Edge>>edges(N);
		for (int i = 0; i < M; ++i) {
			int a, b, c; cin >> a >> b >> c; a--; b--;
			int type;
			if (hs[a] < hs[b]) {
				type = 1;
				edges[a].push_back(Edge{ a,b,c,1 });
			}
			else if (hs[a] == hs[b]) {
				type = 0;
				edges[a].push_back(Edge{ a,b,c,1 });
				edges[b].push_back(Edge{ b,a,c,-1 });
			}
			else {
				type = -1;
				edges[b].push_back(Edge{ b,a,c,-1 });
			}
		}

		vector<vector<long long int>>dp(N, vector<long long int>(N,1e16));
		dp[0][0] = 0;
		priority_queue<aa, vector<aa>, Compare>que;
		que.push(aa{ 0,0,0 });
		long long int ans = -1;
		while (!que.empty()) {
			aa atop(que.top());
			que.pop();
			const int nextup = atop.upnext;
			const int nextdown = atop.downnext;
			const long long int atime = atop.time;
			if (atime >= 1e9)break;
			if (nextup == N - 1 && nextdown == N - 1) {
				ans = atime;
				break;
			}
			if (hs[nextup] == hs[nextdown]) {
				int same_alti = mp[hs[nextup]].size();
				vector<vector<long long int>>memos(N, vector<long long int>(N, 1e16));
				for (int i = 0; i < (1 << same_alti); ++i) {
					bitset<10>bs(i);
					bool ok = true;
					vector<int>canuse(N);
					int feesum = 0;
					for (int j = 0; j < same_alti; ++j) {
						if (mp[hs[nextup]][j] == nextup || mp[hs[nextup]][j] == nextdown) {
							if (!bs[j])ok = false;
						}
						if (bs[j]) {
							canuse[mp[hs[nextup]][j]] = true;
							feesum += moneys[mp[hs[nextup]][j]];
						}
					}
					if (!ok)continue;
					vector<long long int>uptimes(N, 1e9),downtimes(N,1e9);
					{
						vector<long long int>alti_times(N, 1e9);
						alti_times[nextup] = 0;
						priority_queue<aa, vector<aa>, Compare>aque;
						aque.push(aa{ nextup,0,0 });
						int ans = -1;
						while (!aque.empty()) {
							aa atop(aque.top());
							aque.pop();
							const int next = atop.upnext;
							const long long int atime = atop.time;
							for (auto e : edges[next]) {
								if (e.type == 1 && hs[e.src] == hs[e.dst]&&canuse[e.dst]) {
									const long long int nexttime = atime + e.cost;
									if (nexttime < alti_times[e.dst]) {
										alti_times[e.dst] = nexttime;
										aque.push(aa{ e.dst,0,nexttime });
									}
								}
							}
						}
						for (int j = 0; j < same_alti; ++j) {
							const int id = mp[hs[nextup]][j];
							for (auto e : edges[id]) {
								if (e.type == 1&& hs[e.src] != hs[e.dst]) {
									uptimes[e.dst] = min(uptimes[e.dst], alti_times[id] + e.cost);

								}
							}
						}
					}
					{
						vector<long long int>alti_times(N, 1e9);
						alti_times[nextdown] = 0;
						priority_queue<aa, vector<aa>, Compare>aque;
						aque.push(aa{ nextdown,0,0 });
						int ans = -1;
						while (!aque.empty()) {
							aa atop(aque.top());
							aque.pop();
							const int next = atop.upnext;
							const long long int atime = atop.time;
							for (auto e : edges[next]) {
								if (e.type==-1&&hs[e.src]==hs[e.dst] && canuse[e.dst]) {
									const long long int nexttime = atime + e.cost;
									if (nexttime < alti_times[e.dst]) {
										alti_times[e.dst] = nexttime;
										aque.push(aa{ e.dst,0,nexttime });
									}
								}
							}
						}
						for (int j = 0; j < same_alti; ++j) {
							const int id = mp[hs[nextup]][j];
							for (auto e : edges[id]) {
								if (e.type == -1&& hs[e.src] != hs[e.dst]) {
									downtimes[e.dst] = min(downtimes[e.dst], alti_times[id] + e.cost);
								}
							}
						}
					}
					for (int j = 0; j < N; ++j) {
						for (int k = 0; k < N; ++k) {
							memos[j][k] = min(memos[j][k], feesum + uptimes[j] + downtimes[k]);
						}
					}
				}
				for (int j = 0; j < N; ++j) {
					for (int k = 0; k < N; ++k) {
						const long long  int nexttime = memos[j][k] + atime;
						if (nexttime<dp[j][k]) {
							dp[j][k] = nexttime;
							que.push(aa{ j,k,nexttime });
						}
					}
				}
			}
			else if (hs[nextup] > hs[nextdown]) {
				for (auto e : edges[nextdown]) {
					if (e.type ==-1) {
						const long long int nexttime = atime + moneys[nextdown] + e.cost;
						if (dp[nextup][e.dst] > nexttime) {
							dp[nextup][e.dst] = nexttime;
							que.push(aa{ nextup,e.dst,nexttime });
						}
					}
				}
			}
			else {
				for (auto e : edges[nextup]) {
					if (e.type ==1) {
						const long long int nexttime = atime + moneys[nextup]+e.cost;
						if (dp[e.dst][nextdown] > nexttime) {
							dp[e.dst][nextdown] = nexttime;
							que.push(aa{ e.dst,nextdown,nexttime });
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3560