#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Node{
	int cost,height,index;
};

struct Edge{
	Edge(int arg_to,int arg_cost){
		to = arg_to;
		cost = arg_cost;
	}
	int to,cost;
};

struct Info{
	Info(int arg_go_node,int arg_return_node,int arg_state,int arg_sum_cost){
		go_node = arg_go_node;
		return_node = arg_return_node;
		state = arg_state;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{ //総コストの昇順(PQ)
		return sum_cost > arg.sum_cost;
	}

	int go_node,return_node,state,sum_cost;
};

int N,E;
int POW[11];
int height[1001];
int min_cost[50][50][1024];
Node nodes[50];
vector<Edge> G[50],rev_G[50];

void func(){

	for(int i = 0; i < N; i++){
		G[i].clear();
		rev_G[i].clear();
	}
	for(int i = 0; i <= 1000; i++)height[i] = 0;

	nodes[0].height = 0;
	nodes[N-1].height = 1000;

	nodes[0].index = 0;
	nodes[N-1].index = 0;
	nodes[N-1].cost = 0;

	height[0]++;
	height[1000]++;

	for(int i = 1; i <= N-2; i++){
		scanf("%d %d",&nodes[i].cost,&nodes[i].height);
		nodes[i].index = height[nodes[i].height]; //ある高さ内でのインデックスを記録
		height[nodes[i].height]++;
	}

	int from,to,cost;
	for(int loop = 0; loop < E; loop++){
		scanf("%d %d %d",&from,&to,&cost);
		from--;
		to--;
		G[from].push_back(Edge(to,cost));
		rev_G[to].push_back(Edge(from,cost)); //★★帰り道を、逆辺を張ることにより0→N-1方向のグラフにする★★
	}

	//min_cost[goのノード(a)][returnのノード][低い方の、訪れたaと同じ高さの町の集合] = 最小コスト

	for(int i = 0; i <= N-1; i++){
		for(int k = 0; k <= N-1; k++){
			for(int state = 0; state < POW[10]; state++){
				min_cost[i][k][state] = BIG_NUM;
			}
		}
	}

	priority_queue<Info> Q;
	min_cost[0][0][1] = 0;
	Q.push(Info(0,0,1,0));

	int next_node,next_state,next_go,next_return,next_cost;

	while(!Q.empty()){

		if(Q.top().go_node == N-1 && Q.top().return_node == N-1){ //sum_costの昇順にPQを回しているので、解は最初にゴールするはず
			printf("%d\n",Q.top().sum_cost);
			return;
		}else if(Q.top().sum_cost > min_cost[Q.top().go_node][Q.top().return_node][Q.top().state]){
			//printf("不適\n");
			Q.pop();
		}else{

			if(nodes[Q.top().go_node].height <= nodes[Q.top().return_node].height){

				for(int i = 0; i < G[Q.top().go_node].size(); i++){

					next_node = G[Q.top().go_node][i].to;
					if(nodes[Q.top().go_node].height > nodes[next_node].height)continue; //降りる道は通行禁止

					next_cost = Q.top().sum_cost+G[Q.top().go_node][i].cost; //とりあえず道のコストまでは足しておく

					if(nodes[next_node].height > nodes[Q.top().return_node].height){ //go_phaseの方が高くなる場合

						next_state = POW[nodes[Q.top().return_node].index];
						if(nodes[Q.top().go_node].height == nodes[Q.top().return_node].height){ //今、goとreturnが同じ高さ
							next_state |= Q.top().state;
						}
						next_cost += nodes[next_node].cost; //初訪問のはずなのでcostをプラス

					}else if(nodes[next_node].height < nodes[Q.top().return_node].height){

						next_state = POW[nodes[next_node].index];
						if(nodes[next_node].height == nodes[Q.top().go_node].height){ //go_nodeと同じ高さ

							if(Q.top().state & (1 << nodes[next_node].index)){ //訪問済
								//Do nothing
							}else{
								next_cost += nodes[next_node].cost;
							}

							next_state |= Q.top().state;
						}else{
							next_cost += nodes[next_node].cost;
						}

					}else{ //nodes[next_node].height == nodes[Q.top().return_node].height

						next_state = POW[nodes[next_node].index]|POW[nodes[Q.top().return_node].index];
						if(nodes[next_node].height == nodes[Q.top().go_node].height){

							if((Q.top().state & (1 << nodes[next_node].index)) != 0 || next_node == Q.top().return_node){
								//加算済
							}else{
								next_cost += nodes[next_node].cost;
							}
							next_state |= Q.top().state;
						}else{
							if(next_node != Q.top().return_node){
								next_cost += nodes[next_node].cost;
							}
						}
					}

					if(min_cost[next_node][Q.top().return_node][next_state] > next_cost){
						min_cost[next_node][Q.top().return_node][next_state] = next_cost;
						Q.push(Info(next_node,Q.top().return_node,next_state,next_cost));
					}
				}

			}else if(nodes[Q.top().go_node].height > nodes[Q.top().return_node].height){ //return_nodeの方が低い場合

				//printf("retの方が低い\n");

				for(int i = 0; i < rev_G[Q.top().return_node].size(); i++){

					next_node = rev_G[Q.top().return_node][i].to;
					if(nodes[Q.top().return_node].height > nodes[next_node].height)continue; ///★本来は「上り不可」の逆辺なので、下り不可となる

					next_cost = Q.top().sum_cost+rev_G[Q.top().return_node][i].cost; //とりあえず道のコストまでは足しておく

					if(nodes[next_node].height > nodes[Q.top().go_node].height){ //return_phaseの方が高くなる場合

						next_state = POW[nodes[Q.top().go_node].index];
						next_cost += nodes[next_node].cost; //初訪問のはずなのでcostをプラス


					}else if(nodes[next_node].height < nodes[Q.top().go_node].height){

						next_state = POW[nodes[next_node].index];
						if(nodes[next_node].height == nodes[Q.top().return_node].height){ //return_nodeと同じ高さ
							if(Q.top().state & (1 << nodes[next_node].index)){
								//加算済
							}else{
								next_cost += nodes[next_node].cost;
							}
							next_state |= Q.top().state;
						}else{
							next_cost += nodes[next_node].cost;
						}

					}else{ //nodes[next_node].height == nodes[Q.top().go_node].height //★★高さが追いついた場合

							if(next_node == Q.top().go_node){ //同じノードに合流(元の高さは必ずreturnの方が低い)
								next_state = POW[nodes[next_node].index];
								//コストは足さない
							}else{

								//★高さの不等式により、元々go_phaseと高さが同じだった場合はない→高さが追いついたということ
								next_state = POW[nodes[Q.top().go_node].index]|POW[nodes[Q.top().go_node].index];
								next_cost += nodes[next_node].cost;
							}
					}

					if(min_cost[Q.top().go_node][next_node][next_state] > next_cost){
						min_cost[Q.top().go_node][next_node][next_state] = next_cost;
						Q.push(Info(Q.top().go_node,next_node,next_state,next_cost));
					}
				}
			}

			Q.pop();
		}
	}

	printf("-1\n");
}

int main(){

	for(int i = 0; i < 11; i++)POW[i] = pow(2,i);

	while(true){
		scanf("%d %d",&N,&E);
		if(N == 0 && E == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 29612