#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef long long ll;
typedef pair<int, int> PI;

const ll inf = 1e15;
const ll mod = 1000 * 1000 * 1000 + 7;
const double eps = 1e-9;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}

const int MAX = 55;
const int INF = 1e9;
int T[MAX][MAX][1 << 10];

struct State {
  int x;
  int y;
  int mask;
  State(int x_, int y_, int mask_) : x(x_), y(y_), mask(mask_) {}
  friend bool operator<(const State &p, const State &q){
    return p.x != q.x ? p.x < q.y : p.y != q.y ? p.y < q.y : p.mask < q.mask;
  }

  friend bool operator>(const State &p, const State &q){
    return q < p;
  }
};

void solve(int N, int M){
  vector<int> D(N), E(N), I(N);
  REP(i, N - 2) cin >> D[i + 1] >> E[i + 1];
  E[N - 1] = 1000;
  REP(i, N) REP(j, i) if (E[j] == E[i]) I[i]++;
  vector<vector<int> > G(N, vector<int>(N, -1)), H(N, vector<int>(N, -1));
  REP(i, M){
    int a, b, c;
    cin >> a >> b >> c; a--, b--;
    if (E[a] >= E[b]) G[b][a] = c;
    if (E[a] <= E[b]) H[a][b] = c;
  }
  REP(i, MAX) REP(j, MAX) fill(T[i][j], T[i][j] + (1 << 10), INF);
  
  T[0][0][1] = 0;
  priority_queue<pair<int, State> > que;
  que.push(make_pair(0, State(0, 0, 1)));
  while (!que.empty()){
    int x    = que.top().second.x;
    int y    = que.top().second.y;
    int mask = que.top().second.mask;
    int cost = -que.top().first;
    que.pop();
    if (cost > T[x][y][mask]) continue;
    if (x == N - 1 && y == N - 1){
      cout << cost << endl;
      return ;
    }

    if (E[x] <= E[y]){
      REP(z, N) if (H[x][z] != -1){
        int next_cost = cost, next_mask = mask;
        if (E[z] < E[y]){
          next_cost = cost + H[x][z] + D[z];
          next_mask = mask;
        } else if (E[z] > E[y]){
          next_cost = cost + H[x][z] + D[z];
          next_mask = 1 << I[z];
        } else {
          next_cost = cost + H[x][z] + ((mask & (1 << I[z])) ? 0 : D[z]);
          next_mask = mask | (1 << I[z]);
        }

        if (T[z][y][next_mask] > next_cost){
          T[z][y][next_mask] = next_cost;
          que.push(make_pair(-next_cost, State(z, y, next_mask)));
        }
      }
    }
    
    if (E[x] >= E[y]){
      REP(z, N) if (G[y][z] != -1){
        int next_cost = cost, next_mask = mask;
        if (E[z] < E[x]){
          next_cost = cost + G[y][z] + D[z];
          next_mask = mask;
        } else if (E[z] > E[x]){
          next_cost = cost + G[y][z] + D[z];
          next_mask = 1 << I[z];
        } else {
          next_cost = cost + G[y][z] + ((mask & (1 << I[z])) ? 0 : D[z]);
          next_mask = mask | (1 << I[z]);
        }

        if (T[x][z][next_mask] > next_cost){
          T[x][z][next_mask] = next_cost;
          que.push(make_pair(-next_cost, State(x, z, next_mask)));
        }
      }
    }
  }
  cout << -1 << endl;
}

int main(){
  int N, M;
  while (cin >> N >> M && N){
    solve(N, M);
  }
  return 0;
}

Measured memory_bytes: 13988