#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int n, m;
int d[55], e[55];
vector<Pi> G[55];
vector<Pi> rG[55];
int id[55], cnt[1010];

int dp[55][55][1<<10];

struct State {
  int u, v, bit, cost;
  State(){}
  State(int u, int v, int bit, int cost):u(u), v(v), bit(bit), cost(cost){}
  bool operator < (const State& rhs) const {
    return cost > rhs.cost;
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(cin >> n >> m, n || m) {
    rep(i, n) {
      G[i].clear();
      rG[i].clear();
    }
    memset(cnt, 0, sizeof(cnt));
    d[0] = 0; e[0] = 0;
    id[0] = cnt[0]++;
    reps(i, 1, n-1) {
      cin >> d[i] >> e[i];
      id[i] = cnt[e[i]]++;
    }
    d[n-1] = 0; e[n-1] = 1000;
    id[n-1] = cnt[1000]++;
    rep(i, m) {
      int a, b, c;
      cin >> a >> b >> c;
      --a, --b;
      G[a].emplace_back(b, c);
      rG[b].emplace_back(a, c);
    }
    auto dijkstra = [&]() -> int {
      fill((int*)dp[0], (int*)dp[55], inf);
      priority_queue<State> que;
      que.push(State(0, 0, 0, 0));
      while(!que.empty()) {
	State now = que.top(); que.pop();
	//cout<<now.u<<" "<<now.v<<" "<<now.bit<<" "<<now.cost<<endl;
	if(now.u == n-1 && now.v == n-1) return now.cost;
	if(dp[now.u][now.v][now.bit] < now.cost) continue;
	if(e[now.u] <= e[now.v]) {
	  for(Pi p : G[now.u]) {
	    State nxt = now;
	    if(e[now.u] > e[p.first]) continue;
	    if(e[now.v] != e[p.first]) {
	      nxt.u = p.first;
	      nxt.bit = 0;
	      nxt.cost += p.second+d[p.first];
	    } else if((now.bit>>id[p.first])&1) {
	      nxt.u = p.first;
	      nxt.cost += p.second;
	    } else {
	      nxt.u = p.first;
	      nxt.bit |= (1<<id[p.first]) | (1<<id[now.v]);
	      nxt.cost += p.second+(p.first == now.v ? 0 : d[p.first]);
	    }
	    if(nxt.cost < dp[nxt.u][nxt.v][nxt.bit]) {
	      dp[nxt.u][nxt.v][nxt.bit] = nxt.cost;
	      que.emplace(nxt);
	    }
	  }
	}
	if(e[now.u] >= e[now.v]) {
	  for(Pi p : rG[now.v]) {
	    State nxt = now;
	    if(e[now.v] > e[p.first]) continue;
	    if(e[now.u] != e[p.first]) {
	      nxt.v = p.first;
	      nxt.bit = 0;
	      nxt.cost += p.second+d[p.first];
	    } else if((now.bit>>id[p.first])&1) {
	      nxt.v = p.first;
	      nxt.cost += p.second;
	    } else {
	      nxt.v = p.first;
	      nxt.bit |= (1<<id[p.first]) | (1<<id[now.u]);
	      nxt.cost += p.second+(p.first == now.u ? 0 : d[p.first]);
	    }
	    if(nxt.cost < dp[nxt.u][nxt.v][nxt.bit]) {
	      dp[nxt.u][nxt.v][nxt.bit] = nxt.cost;
	      que.emplace(nxt);
	    }
	  }
	}
      }
      return -1;
    };
    cout << dijkstra() << endl;
  }

  return 0;
}

