#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3
#define mod 1000000007

struct state{
  int u,v,S,d;
};
bool operator<(const state& a,const state& b){return a.d > b.d;}

int N,M;
int dist[50][50][1<<10];

int main(){
  while(1){
    cin>>N>>M;
    if(N==0)break;
    vector<P> g[N],rg[N];
    vector<int> A(N),F(N);
    A[0]=0; F[0]=0;
    A[N-1]=1000; F[N-1]=0;
    repl(i,1,N-1)cin>>F[i]>>A[i];
    rep(i,M){
      int a,b,c;
      cin>>a>>b>>c;
      a--;b--;
      g[a].push_back(P(b,c));
      rg[b].push_back(P(a,c));
    }
    
    vector<vector<int> > idx(1001);
    vector<int> ord(N);
    rep(i,N){
      ord[i]=idx[A[i]].size();
      idx[A[i]].push_back(i);
    }

    rep(i,N)rep(j,N)rep(S,1<<10)dist[i][j][S]=INF;
    priority_queue<state> que;
    que.push((state){0,0,1,0});
    while(que.size()){
      state s=que.top(); que.pop();
      if(dist[s.u][s.v][s.S]!=INF)continue;
      dist[s.u][s.v][s.S]=s.d;
      if(A[s.u]<A[s.v]){
        for(P e : g[s.u]){
          if(A[s.u]>A[e.fi])continue;
          if(A[e.fi]==A[s.v]){
            que.push((state){e.fi,s.v,(1<<ord[e.fi])|(1<<ord[s.v]),s.d+e.se+(e.fi!=s.v?F[e.fi]:0)});
          }else que.push((state){e.fi,s.v,0,s.d+e.se+F[e.fi]});
        }
      }else if(A[s.u]>A[s.v]){
        for(P e : rg[s.v]){
          if(A[s.v]>A[e.fi])continue;
          if(A[e.fi]==A[s.u]){
            que.push((state){s.u,e.fi,(1<<ord[e.fi])|(1<<ord[s.u]),s.d+e.se+(e.fi!=s.u?F[e.fi]:0)});
          }else que.push((state){s.u,e.fi,0,s.d+e.se+F[e.fi]});
        }
      }else{
        for(P e : g[s.u]){
          if(A[s.u]>A[e.fi])continue;
          if(A[e.fi]==A[s.v]){
            que.push((state){e.fi,s.v,s.S|(1<<ord[e.fi]),s.d+e.se+((s.S&(1<<ord[e.fi]))==0?F[e.fi]:0)});
          }else que.push((state){e.fi,s.v,0,s.d+e.se+F[e.fi]});
        }
        for(P e : rg[s.v]){
          if(A[s.v]>A[e.fi])continue;
          if(A[e.fi]==A[s.u]){
            que.push((state){s.u,e.fi,s.S|(1<<ord[e.fi]),s.d+e.se+((s.S&(1<<ord[e.fi]))==0?F[e.fi]:0)});
          }else que.push((state){s.u,e.fi,0,s.d+e.se+F[e.fi]});
        }
      }
    }

    if(dist[N-1][N-1][1]==INF)cout<<-1<<endl;
    else cout<<dist[N-1][N-1][1]<<endl;
  }
  return 0;
}

