#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<int, pi> ip;
typedef pair<double, pi> pdp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;

int n, m;
int d[50], h[50];
vector<pi> e[50], re[50];
int dist[50][50];

void solve() {
    rep(i,n) rep(j,n) dist[i][j] = inf;
    dist[0][0] = 0;
    rep(i,n) e[i].clear();
    rep(i,n) re[i].clear();
    d[0] = 0; h[0] = 0;
    rep(i,n-2) cin >> d[i+1] >> h[i+1];
    d[n-1] = 0; h[n-1] = 1000;
    set<int> hoge;
    rep(i,n) hoge.insert(h[i]);
    rep(i,m) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        if (h[a] >= h[b]) {
            re[b].push_back(pi(a, c));
        }
        if (h[a] <= h[b]) {
            e[a].push_back(pi(b, c));
        }
    }
    //rep(i,n) cerr << e[i].size() << " " << re[i].size() << endl;
    for (auto it = hoge.begin(); it != hoge.end(); it++) {
        int now[10], n_cnt = 0;
        bool ok[50];
        rep(i,n) {
            if (h[i] == (*it)) {
                now[n_cnt++] = i;
            }
        }
        int newdist[50][50];
        rep(i,n) rep(j,n) newdist[i][j] = inf;
        for (int i = 0; i < (1<<n_cnt); i++) {
            rep(j,n) ok[j] = false;
            int d_cost = 0;
            rep(j,n_cnt) if ((1<<j)&i) {
                d_cost += d[now[j]];
                ok[now[j]] = true;
            }
            priority_queue<ip, vector<ip>, greater<ip>> pque;
            rep(j,n) rep(k,n) {
                if (dist[j][k] != inf) pque.push(ip(dist[j][k]+d_cost, pi(j,k)));
            }
            int tmpdist[50][50];
            rep(j,n) rep(k,n) tmpdist[j][k] = inf;
            while (!pque.empty()) {
                int cos = pque.top().first, x = pque.top().second.first, y = pque.top().second.second;
                //cerr << cos << " " << x << " " << y << " " << e[x].size() << " " << re[y].size() << endl;
                pque.pop();
                rep(j,e[x].size()) {
                    if (!ok[e[x][j].first]) continue;
                    if (tmpdist[e[x][j].first][y] > cos + e[x][j].second) {
                        tmpdist[e[x][j].first][y] = cos + e[x][j].second;
                        pque.push(ip(tmpdist[e[x][j].first][y], pi(e[x][j].first, y)));
                    }
                }
                rep(j,re[y].size()) {
                    if (!ok[re[y][j].first]) continue;
                    if (tmpdist[x][re[y][j].first] > cos + re[y][j].second) {
                        tmpdist[x][re[y][j].first] = cos + re[y][j].second;
                        pque.push(ip(tmpdist[x][re[y][j].first], pi(x, re[y][j].first)));
                    }
                }
                /*
                rep(_i,n) {
                    rep(j,n) {
                        cerr << dist[_i][j] << " ";
                    }
                    cerr << endl;
                }
                */
            }
            rep(j,n) rep(k,n) newdist[j][k] = min(newdist[j][k], tmpdist[j][k]);
        }
        rep(i,n) rep(j,n) dist[i][j] = min(dist[i][j], newdist[i][j]);
        /*
        rep(i,n) {
            rep(j,n) {
                cerr << dist[i][j] << " ";
            }
            cerr << endl;
        }
        */
    }
    if (dist[n-1][n-1] == inf) dist[n-1][n-1] = -1;
    cout << dist[n-1][n-1] << endl;
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
    cout.precision(20);
    cerr << fixed;
    cerr.precision(6);
#ifdef LOCAL
    //freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif  
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        solve();
    }
    //cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}



Measured memory_bytes: 3188