// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

int n,m;
int d[55],e[55];
int up[55][55];
int dw[55][55];
int same[55][55];
int cost1u[55][55];
int cost1d[55][55];
int cost2[55][55][55][55];
ll dp[55][55];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	while(cin>>n>>m && n){
		rep(i,n)rep(j,n)up[i][j]=dw[i][j]=same[i][j]=INF;
		map<int,vi> alt;
		rep2(i,1,n-1){
			cin>>d[i]>>e[i];
			alt[e[i]].pb(i);
		}
		d[0] = d[n-1] = 0;
		e[0] = 0;
		e[n-1] = 1000;
		alt[0].pb(0);
		alt[1000].pb(n-1);
		rep(i,m){
			int a,b,c;
			cin>>a>>b>>c;
			a--;b--;
			if(e[a] < e[b]){
				up[a][b] = c;
			}
			else if(e[a] > e[b]){
				dw[a][b] = c;
			}
			else{
				same[a][b] = c;
			}
		}

		foreach(it,alt){
			vi &town = it->sec;
			int dist[11][11];
			rep(i,sz(town))rep(j,sz(town)){
				dist[i][j] = i==j ? 0 : same[town[i]][town[j]] + d[town[j]];
			}
			rep(k,sz(town))rep(i,sz(town))rep(j,sz(town)){
				dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
			}
			rep(i,sz(town))rep(j,sz(town)){
				cost1u[town[i]][town[j]] = dist[i][j];
			}
			rep(i,sz(town))rep(j,sz(town)){
				dist[i][j] = i==j ? 0 : same[town[i]][town[j]] + d[town[i]];
			}
			rep(k,sz(town))rep(i,sz(town))rep(j,sz(town)){
				dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
			}
			rep(i,sz(town))rep(j,sz(town)){
				cost1d[town[i]][town[j]] = dist[i][j];
			}
			rep(i,sz(town))rep(j,sz(town))rep(k,sz(town))rep(l,sz(town)){
				cost2[town[i]][town[j]][town[k]][town[l]] = INF;
			}
			rep(mask,1<<sz(town)){
				rep(i,sz(town))rep(j,sz(town)){
					dist[i][j] = (mask>>i&1) & (mask>>j&1) ?
					(i==j ? 0 : same[town[i]][town[j]]) : INF;
				}
				rep(k,sz(town))rep(i,sz(town))rep(j,sz(town)){
					dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
				}
				int visa = 0;
				rep(i,sz(town))if(mask>>i&1)visa += d[town[i]];
				rep(i,sz(town))rep(j,sz(town))rep(k,sz(town))rep(l,sz(town)){
					if(!(mask>>i&1) || !(mask>>j&1))continue;
					int v = visa;
					if(i == j) v -= d[town[i]];
					else v -= d[town[i]] + d[town[j]];
					cost2[town[i]][town[j]][town[k]][town[l]] =
					min(cost2[town[i]][town[j]][town[k]][town[l]],
						dist[i][k] + dist[l][j] + v);
					//cout<<mask<<" "<<town[i]<<town[j]<<town[k]<<town[l]<<" "<<cost2[town[i]][town[j]][town[k]][town[l]]<<endl;
				}
			}
		}

		rep(i,n)rep(j,n)dp[i][j]=INF;
		dp[0][0]=0;
		foreach(it1,alt)foreach(it2,alt){
			int al1 = it1->fir, al2 = it2->fir;
			vi &town1 = it1->sec, &town2 = it2->sec;

			if(al1 == al2){
				rep(i,sz(town1))rep(j,sz(town2)){
					int t1 = town1[i], t2 = town2[j];
					rep(ii,sz(town1))rep(jj,sz(town2)){
						dp[t1][t2] = min(dp[t1][t2],
							dp[town1[ii]][town2[jj]]
							+ cost2[town1[ii]][town2[jj]][t1][t2]);
					}
				}
			}
			else{
				rep(i,sz(town1))rep(j,sz(town2)){
					int t1 = town1[i], t2 = town2[j];
					rep(ii,sz(town1))rep(jj,sz(town2)){
						dp[t1][t2] = min(dp[t1][t2],
							dp[town1[ii]][town2[jj]]
							+ cost1u[town1[ii]][t1]
							+ cost1d[t2][town2[jj]]);
					}
				}
			}

			rep(i,sz(town1))rep(j,sz(town2)){
				int t1 = town1[i], t2 = town2[j];
				//cout<<t1<<" "<<t2<<" : "<<dp[t1][t2]<<endl;
				rep(ii,n){
					dp[ii][t2] = min(dp[ii][t2], dp[t1][t2] + up[t1][ii]
						+ (ii == t2 ? 0 : d[ii]));
					dp[t1][ii] = min(dp[t1][ii], dp[t1][t2] + dw[ii][t2]
						+ (ii == t1 ? 0 : d[ii]));
				}
			}
		}

		//rep(i,n)rep(j,n)cout<<i<<" "<<j<<" : "<<dp[i][j]<<endl;

		int ans=dp[n-1][n-1];
		if(ans<INF/2)cout<<ans<<endl;
		else cout<<-1<<endl;
	}
}

Measured memory_bytes: 32276