#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <sstream>

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
const double EPS=1e-6;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int)((a).size())
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) a.rbegin(),a.rend()
#define FLL(a,b) memset((a),b,sizeof(a))
#define CLR(a) FLL(a,0)
#define declare(a,it) __typeof(a) it=(a)
#define FOR(it,a) for(declare(a.begin(),it);it!=a.end();++it)
#define FORR(it,a) for(declare(a.rbegin(),it);it!=a.rend();++it)
template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,-1,1,1,-1};
int s2i(string& a){stringstream ss(a);int r;ss>>r;return r;}
int geti(){int n;scanf("%d", &n);return n;}

bool vis[50][50][1<<10];
int d[100],e[100];
int num[1100];
int idx[100];
vector<PI> G[100],rG[100];

int memo[50][50][1<<10];
int n,m;

int main(int argc, char *argv[])
{
  while(cin >> n >> m && (n|m)){
    e[n-1] = 1000;
    d[n-1] = 0;
    memset(num,0,sizeof(num));
    memset(idx,0,sizeof(idx));
    rep(i,n-2){
      cin >> d[i+1] >> e[i+1];
      idx[i+1] = num[e[i+1]];
      ++num[e[i+1]];
    }
    rep(i,n) G[i].clear();
    rep(i,n) rG[i].clear();
    
    rep(i,m){
      int a,b,c;
      cin >> a >> b >> c;
      --a,--b;
      if(e[a] <= e[b]) G[a].pb(mp(b,c));
      if(e[a] >= e[b]) rG[b].pb(mp(a,c));
    }
    
    memset(memo, -1, sizeof(memo));
    int ans = 1<<28;
    
    memset(vis,0,sizeof(vis));
    rep(i,n)rep(j,n)rep(k,1<<10) memo[i][j][k] = 1<<28;

    queue<pair<pair<int,short>,pair<char,char> > > q;
    memo[0][0][1] = 0;
    vis[0][0][1] = 1;
    q.push(mp(mp(0,1),mp(0,0)));

    int cnt  = 0;
    while(!q.empty()){
      int cc = q.front().F.F;
      int st = q.front().F.S;
      int cv1 = q.front().S.F;
      int cv2 = q.front().S.S;
      q.pop();
      
      vis[cv1][cv2][st] = 0;
      
      cc = memo[cv1][cv2][st];
      if(cc >= ans) continue;
      if(cv1 == n-1 && cv2 == n-1){
        if(ans == -1) ans = 1<<28;
        ans = min(ans, cc);
        //break;
      }
      
      int mia = min(e[cv1], e[cv2]);
      if(mia == e[cv1]){
        for(auto ed : G[cv1]){
          int nc = cc + ed.S + d[ed.F];
          if((e[ed.F] == mia && ((st>>idx[ed.F])&1)) || ed.F == cv2)
            nc -= d[ed.F];
          int nst = st;
          int nmia = min(e[ed.F], e[cv2]);
          if(mia != nmia)
            nst = 0;
          
          if(nmia == e[ed.F]) nst |= 1 << idx[ed.F];
          if(nmia == e[cv2]) nst |= 1 << idx[cv2];
          if(nc < memo[ed.F][cv2][nst] && nc < ans){
            memo[ed.F][cv2][nst] = nc;
            if(!vis[ed.F][cv2][nst]){
              vis[ed.F][cv2][nst] = 1;              
              q.push(mp(mp(nc,nst),mp(ed.F,cv2)));
            }
          }
        }
      }
      
      if(mia == e[cv2]){
        for(auto ed : rG[cv2]){
          int nc = cc + ed.S + d[ed.F];
          if((e[ed.F] == mia && ((st>>idx[ed.F])&1)) || ed.F == cv1)
            nc -= d[ed.F];
          int nst = st;
          int nmia = min(e[ed.F], e[cv1]);
          if(mia != nmia)
            nst = 0;
          
          if(nmia == e[ed.F]) nst |= 1 << idx[ed.F];
          if(nmia == e[cv1]) nst |= 1 << idx[cv1];
          if(nc < memo[cv1][ed.F][nst] && nc < ans){
            memo[cv1][ed.F][nst] = nc;
            if(!vis[cv1][ed.F][nst]){
              vis[cv1][ed.F][nst] = 1;
              q.push(mp(mp(nc,nst),mp(cv1,ed.F)));
            }
          }
        }
      }      
    }
    if(ans == (1<<28)) ans = -1;
    cout << ans << endl;
  }
}

Measured memory_bytes: 16832