#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007 /5;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
const long double epsA=1e-4;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}


bool solve(void){
	int i,j,k,n,m;cin>>n>>m;
	if(n==0){return false;}
	//行き、帰り、両用
	//1024それぞれについて,それが使える場合の距離別コスト
	vector<tuple<int,int,int>>zyou(n);
	zyou[0]=mt(0,0,0);
	zyou[n-1]=mt(1000,0,n-1);
	for(i=1;i<n-1;i++){int d,e;cin>>d>>e;zyou[i]=mt(e,d,i);}
	SO(zyou);
	vector<int>name(n);
	vector<int>fee(n);
	vector<int>atli(n);
	int maeati=-1,aaa=-1;
	int stati[51];
	for(i=0;i<n;i++){
		name[get<2>(zyou[i])]=i;
		fee[i]=get<1>(zyou[i]);
		if(maxeq(maeati,get<0>(zyou[i]))){aaa++;stati[aaa]=i;}
		atli[i]=aaa;
	}
	aaa++;stati[aaa]=n;
	int Acost[50][50];
	int Bcost[50][50];
	int Ccost[50][50];
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			Acost[i][j]=mod;
			Bcost[i][j]=mod;
			Ccost[i][j]=mod;
		}
		Acost[i][i]=0;
		Bcost[i][i]=0;
		Ccost[i][i]=0;
	}
	
	for(i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;a--;b--;
		a=name[a];b=name[b];
		if(atli[a]<atli[b]){Acost[a][b]=c;}
		if(atli[b]<atli[a]){Bcost[b][a]=c;}
		if(atli[a]==atli[b]){Ccost[a][b]=c;}
	}
	static int Scost[50][10][10][10][10];//same attitude cost
	static int Kcost[50][10][10];//same attitude cost
	for(i=0;i<aaa;i++){
		int kaz=stati[i+1]-stati[i];
		int z,x,c,v;
		for(z=0;z<kaz;z++){
			for(x=0;x<kaz;x++){
				Kcost[i][z][x]=mod;
				for(c=0;c<kaz;c++){
					for(v=0;v<kaz;v++){
						Scost[i][z][x][c][v]=mod;
					}
				}
			}
		}
		for(int bi=0;bi<(1<<kaz);bi++){
			static int Ncost[10][10];
			
			for(z=0;z<kaz;z++){
				for(x=0;x<kaz;x++){Ncost[z][x]=mod;}
			}
			int Sfee=0;
			for(z=0;z<kaz;z++){
				if((bi&(1<<z))==0){continue;}
				Sfee+=fee[stati[i]+z];
				for(x=0;x<kaz;x++){
					if((bi&(1<<x))==0){continue;}
					Ncost[z][x]=Ccost[stati[i]+z][stati[i]+x];
				}
				Ncost[z][z]=0;
			}
			for(z=0;z<kaz;z++){
				for(x=0;x<kaz;x++){
					for(c=0;c<kaz;c++){
						mineq(Ncost[x][c],Ncost[x][z]+Ncost[z][c]);
					}
				}
			}
			for(z=0;z<kaz;z++){
				for(x=0;x<kaz;x++){
					mineq(Kcost[i][z][x],Sfee+Ncost[z][x]);
					for(c=0;c<kaz;c++){
						for(v=0;v<kaz;v++){
							mineq(Scost[i][z][x][c][v],Sfee+Ncost[z][x]+Ncost[v][c]);
						}
					}
				}
			}
		}
	}
	//同じ高さの計算をした
	//高さごとにうまくやるDP
	int dp[50][50];
	int Adp[50][50];
	int Bdp[50][50];
	int ABdp[50][50];
	//AB 未払いのvisa料金
	/*for(i=0;i<n;i++){
		cerr<<"i="<<i<<" Kcost="<<Kcost[i][0][0]<<endl;
		cerr<<"i="<<i<<" Scost="<<Scost[i][0][0][0][0]<<endl;
	}*/
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){dp[i][j]=mod;Adp[i][j]=mod;Bdp[i][j]=mod;ABdp[i][j]=mod;}
	}
	dp[0][0]=0;
	for(int a=0;a<aaa;a++){
		int As=stati[a],At=stati[a+1];
		for(int b=0;b<aaa;b++){
			int Bs=stati[b],Bt=stati[b+1];
			//料金の支払い
			int z,x,c,v;
			for(z=As;z<At;z++){
				for(x=Bs;x<Bt;x++){
					for(c=Bs;c<Bt;c++){
						mineq(dp[z][c],Bdp[z][x]+Kcost[b][c-Bs][x-Bs]);
					}
				}
			}
			for(z=Bs;z<Bt;z++){
				for(x=As;x<At;x++){
					for(c=As;c<At;c++){
						mineq(dp[c][z],Adp[x][z]+Kcost[a][x-As][c-As]);
					}
				}
			}
			if(a==b){
				for(z=As;z<At;z++){
					for(x=As;x<At;x++){
						for(c=Bs;c<Bt;c++){
							for(v=Bs;v<Bt;v++){
								mineq(dp[x][v],ABdp[z][c]+Scost[a][z-As][x-As][c-Bs][v-Bs]);
							}
						}
					}
				}
			}
			//配るDP
			for(z=Bs;z<Bt;z++){
				for(x=As;x<At;x++){
					for(c=At;c<n;c++){
						mineq(Adp[c][z],dp[x][z]+Acost[x][c]);
					}
				}
			}
			for(z=As;z<At;z++){
				for(x=Bs;x<Bt;x++){
					for(c=Bt;c<n;c++){
						mineq(Bdp[z][c],dp[z][x]+Bcost[x][c]);
					}
				}
			}
			
			for(x=At;x<n;x++){
				for(v=Bt;v<n;v++){
					if(atli[x]!=atli[v]){continue;}
					for(z=As;z<At;z++){
						for(c=Bs;c<Bt;c++){
							mineq(ABdp[x][v],dp[z][c]+Acost[z][x]+Bcost[c][v]);
						}
					}
				}
			}
		}
	}
	/*for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cerr<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
			cerr<<"Adp["<<i<<"]["<<j<<"]="<<Adp[i][j]<<endl;
			cerr<<"Bdp["<<i<<"]["<<j<<"]="<<Bdp[i][j]<<endl;
			cerr<<"ABdp["<<i<<"]["<<j<<"]="<<ABdp[i][j]<<endl;
		}
	}*/
	if(dp[n-1][n-1]>=mod){dp[n-1][n-1]=-1;}
	cout<<dp[n-1][n-1]<<endl;
	return true;
}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	while(solve()){}
	return 0;
}


Measured memory_bytes: 3764