#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int inf=1e8;
int dp[50][50][1<<10];
int f[50],h[50],c[50][50];
vector<int> hs;
vector<int> vc[50];
int id[50];
void init(){
	hs.clear();
	rep(i,50) vc[i].clear();
	rep(i,50) rep(j,50) rep(k,1<<10) dp[i][j][k]=inf;
	dp[0][0][1]=0;
	rep(i,50) rep(j,50) c[i][j]=inf;
}
int main(){
	while(true){
		int N,M;
		cin>>N>>M;
		if(N==0) break;
		init();
		f[0]=f[N-1]=0;
		h[0]=0,h[N-1]=1000;
		rep1(i,N-2) cin>>f[i]>>h[i];
		rep(i,N) hs.pb(h[i]);
		sort(all(hs));
		hs.erase(unique(all(hs)),hs.end());
		rep(i,N){
			h[i]=lower_bound(all(hs),h[i])-hs.begin();
			id[i]=vc[h[i]].size();
			vc[h[i]].pb(i);
		}
		int H=hs.size();
		rep(i,M){
			int a,b,x;
			cin>>a>>b>>x;
			a--,b--;
			c[a][b]=x;
		}
		rep(i,H) rep(j,H){
			int m=max(i,j);
			int K=vc[m].size();
			rep(b,1<<K){
				rep(I,vc[i].size()) rep(J,vc[j].size()){
					int v=vc[i][I],u=vc[j][J];
					if(i==j){
						rep(nv,N){
							if(h[nv]<h[v]) continue;
							if(h[nv]==j){
								if((b>>id[nv])&1) chmin(dp[nv][u][b],dp[v][u][b]+c[v][nv]);
								else chmin(dp[nv][u][b|(1<<id[nv])],dp[v][u][b]+c[v][nv]+f[nv]);
							}else if(h[nv]>i){
								chmin(dp[nv][u][1<<id[nv]],dp[v][u][b]+c[v][nv]+f[nv]);
							}
						}
						rep(nu,N){
							if(h[nu]<h[u]) continue;
							if(h[nu]==i){
								if((b>>id[nu])&1) chmin(dp[v][nu][b],dp[v][u][b]+c[nu][u]);
								else chmin(dp[v][nu][b|(1<<id[nu])],dp[v][u][b]+c[nu][u]+f[nu]);
							}else if(h[nu]>j){
								chmin(dp[v][nu][1<<id[nu]],dp[v][u][b]+c[nu][u]+f[nu]);
							}
						}
					}
					if(i<j){
						rep(nv,N){
							if(h[nv]<h[v]) continue;
							if(h[nv]==h[u]){
								if((b>>id[nv])&1) chmin(dp[nv][u][b],dp[v][u][b]+c[v][nv]);
								else chmin(dp[nv][u][b|(1<<id[nv])],dp[v][u][b]+c[v][nv]+f[nv]);
							}else if(h[nv]<j){
								chmin(dp[nv][u][b],dp[v][u][b]+c[v][nv]+f[nv]);
							}else{
								chmin(dp[nv][u][1<<id[nv]],dp[v][u][b]+c[v][nv]+f[nv]);
							}
						}
						rep(nu,N){
							if(h[nu]<h[u]) continue;
							if(h[nu]==h[u]){
								if((b>>id[nu])&1) chmin(dp[v][nu][b],dp[v][u][b]+c[nu][u]);
								else chmin(dp[v][nu][b|(1<<id[nu])],dp[v][u][b]+c[nu][u]+f[nu]);
							}else{
								chmin(dp[v][nu][1<<id[nu]],dp[v][u][b]+c[nu][u]+f[nu]);
							}
						}
					}
					if(i>j){
						rep(nv,N){
							if(h[nv]<h[v]) continue;
							if(h[nv]==h[v]){
								if((b>>id[nv])&1) chmin(dp[nv][u][b],dp[v][u][b]+c[v][nv]);
								else chmin(dp[nv][u][b|(1<<id[nv])],dp[v][u][b]+c[v][nv]+f[nv]);
							}else{
								chmin(dp[nv][u][1<<id[nv]],dp[v][u][b]+c[v][nv]+f[nv]);
							}
						}
						rep(nu,N){
							if(h[nu]<h[u]) continue;
							if(h[nu]==h[v]){
								if((b>>id[nu])&1) chmin(dp[v][nu][b],dp[v][u][b]+c[nu][u]);
								else chmin(dp[v][nu][b|(1<<id[nu])],dp[v][u][b]+c[nu][u]+f[nu]);
							}else if(h[nu]<h[v]){
								chmin(dp[v][nu][b],dp[v][u][b]+c[nu][u]+f[nu]);
							}else{
								chmin(dp[v][nu][1<<id[nu]],dp[v][u][b]+c[nu][u]+f[nu]);
							}
						}
					}
				}
			}
		}
		if(dp[N-1][N-1][1]==inf) puts("-1");
		else cout<<dp[N-1][N-1][1]<<endl;
	}
}

Measured memory_bytes: 11228