// 2011アジア地区予選 J : Round Trip

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

typedef vector< vector< pair<int, int> > > graph;

class Node{
public:
	int apos, bpos, visit, cost;
	Node(int apos, int bpos, int visit, int cost) : apos(apos), bpos(bpos), visit(visit), cost(cost) {}
	bool operator < (const Node &nd) const { return cost > nd.cost; }
};

int main(){
	int n, m;
	static int dp[50][50][1024];
	int d[50], e[50];
	int num[1001], idx[50];
	while(cin >> n >> m, n){
		memset(num, 0, sizeof(num));
		d[0  ] = 0; e[0  ] = 0;
		idx[0] = num[0]++;
		for(int i=1;i<n-1;i++){
			cin >> d[i] >> e[i];
			idx[i] = num[e[i]]++;
		}
		d[n-1] = 0; e[n-1] = 1000;
		idx[n-1] = num[1000]++;
		graph ga(n), gb(n);
		for(int i=0;i<m;i++){
			int a, b, c; cin >> a >> b >> c;
			if(e[a-1]<=e[b-1]) ga[a-1].push_back(make_pair(b-1, c));
			if(e[a-1]>=e[b-1]) gb[b-1].push_back(make_pair(a-1, c));
		}

		memset(dp, -1, sizeof(dp));
		priority_queue<Node> qu; qu.push(Node(0, 0, 1, 0));
		dp[0][0][1] = 0;
		int res = -1;
		while(!qu.empty()){
			Node nd = qu.top(); qu.pop();
			int apos = nd.apos, bpos = nd.bpos, visit = nd.visit, cost = nd.cost;
			if(dp[apos][bpos][visit] < cost) continue;
			if(apos == n-1 && bpos == n-1){
				res = cost;
				break;
			}

			if(e[apos] >= e[bpos]){
				for(int i=0;i<gb[bpos].size();i++){
					int next = gb[bpos][i].first;
					int add  = gb[bpos][i].second;
					if(!(e[next] == e[apos] && (visit&(1<<idx[next])))) add += d[next]; 

					int nvisit = visit;
					if(e[next] == e[apos] && !(visit&(1<<idx[next]))) nvisit |= 1<<idx[next];
					if(e[next] > e[apos]) nvisit = 1<<idx[next];

					if(dp[apos][next][nvisit] == -1 || dp[apos][next][nvisit] > dp[apos][bpos][visit] + add){
						dp[apos][next][nvisit] = dp[apos][bpos][visit] + add;
						qu.push(Node(apos, next, nvisit, dp[apos][next][nvisit]));
					}
				}
			}
			if(e[apos] <= e[bpos]){
				for(int i=0;i<ga[apos].size();i++){
					int next = ga[apos][i].first;
					int add  = ga[apos][i].second;
					if(!(e[next] == e[bpos] && (visit&(1<<idx[next])))) add += d[next]; 

					int nvisit = visit;
					if(e[next] == e[bpos] && !(visit&(1<<idx[next]))) nvisit |= 1<<idx[next];
					if(e[next] > e[bpos]) nvisit = 1<<idx[next];

					if(dp[next][bpos][nvisit] == -1 || dp[next][bpos][nvisit] > dp[apos][bpos][visit] + add){
						dp[next][bpos][nvisit] = dp[apos][bpos][visit] + add;
						qu.push(Node(next, bpos, nvisit, dp[next][bpos][nvisit]));
					}
				}
			}
		}
		cout << res << endl;
	}
}