// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

class range {
    struct Iterator {
        int val, inc;
        int operator*() {return val;}
        bool operator!=(Iterator& rhs) {return val < rhs.val;}
        void operator++() {val += inc;}
    };
    Iterator i, n;
    public:
    range(int e) : i({0, 1}), n({e, 1}) {}
    range(int b, int e) : i({b, 1}), n({e, 1}) {}
    range(int b, int e, int inc) : i({b, inc}), n({e, inc}) {}
    Iterator& begin() {return i;}
    Iterator& end() {return n;}
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

const int INF = 1e8;

void calc1(int dp1[1 << 10][10][10], int g1[55][55], vector<int> vs) {
    int V = vs.size();
    REP(s, 1<<V) {
        REP(i, V) REP(j, V) dp1[s][i][j] = g1[ vs[i] ][ vs[j] ];
        REP(i, V) if(!(s >> i & 1)) REP(j, V) dp1[s][i][j] = dp1[s][j][i] = INF;

        REP(k, V) REP(i, V) REP(j, V) dp1[s][i][j] = min(dp1[s][i][j], dp1[s][i][k] + dp1[s][k][j]);
    }
}

int main(){
    iostream_init();
    int N, M;
    while(cin >> N >> M && N > 0) {
        // cout << "---" << endl;

        int g1[55][55] = {};
        int g2[55][55] = {};
        REP(i, N) REP(j, N) g1[i][j] = (i == j ? 0 : INF);
        REP(i, N) REP(j, N) g2[i][j] = (i == j ? 0 : INF);

        vector<int> d(N); // visa
        vector<int> h(N);
        h[0] = 0;
        h[N-1] = 1000;

        REP(i, N-2) cin >> d[i+1] >> h[i+1];

        map<int, vector<int>> vsm;
        REP(i, N) vsm[ -h[i] ].push_back(i);

        REP(i, M) {
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            g1[a][b] = c;
            g2[b][a] = c;
        }

        int dp[55][55] = {};
        REP(i, N) REP(j, N) dp[i][j] = INF;
        dp[N-1][N-1] = 0;

        for(auto p : vsm) {
            if(p.first == -1000){
                assert(p.second.size() == 1 && p.second.front() == N-1);
                continue;
            }
            // cout << p.first << " " << "{{{}}}" << endl;
            //REP(i, p.second.size()) cout << p.second[i] << endl;
            // cout << "{{{}}}" << endl;

            int ndp[55][55] = {};
            REP(u, N) REP(v, N) ndp[u][v] = INF;

            const vector<int> vs = p.second;
            const int V = vs.size();

            int dp1[1 << 10][10][10];
            calc1(dp1, g1, vs);
            int dp2[1 << 10][10][10];
            calc1(dp2, g2, vs);
            // REP(s, 1<<V) REP(i, V) REP(j, V)cout << i << " " << j << " " << dp1[s][i][j] << endl;

            int dp3[10][10][10][10];
            REP(u, V) REP(v, V) REP(a, V) REP(b, V) dp3[u][v][a][b] = INF;
            REP(s, 1<< V) {
                int cost = 0;
                REP(i, V) if(s >> i & 1) cost += d[ vs[i] ];
                REP(u, V) REP(a, V) REP(v, V) REP(b, V) {
                    dp3[u][v][a][b] = min(dp3[u][v][a][b], cost + dp1[s][u][a] + dp2[s][v][b]);
                }
            }
            // REP(u, V) REP(v, V) REP(a, V) REP(b, V) printf("%d %d %d %d %d\n", u, v, a, b, dp3[u][v][a][b]);

            REP(u, N) REP(v, N) if(dp[u][v] < INF) {
                ndp[u][v] = min(ndp[u][v], dp[u][v]);
                REP(i, V) REP(j, V) {
                    const int a = vs[i];
                    const int b = vs[j];
                    REP(k, V) REP(l, V) {
                        const int am = vs[k];
                        const int bm = vs[l];
                        ndp[a][b] = min(ndp[a][b], dp[u][v] + g1[u][am] + g2[v][bm] + dp3[k][l][i][j]);

                        ndp[u][b] = min(ndp[u][b], dp[u][v] + g2[v][bm] + dp3[j][l][j][j]);
                        ndp[a][v] = min(ndp[a][v], dp[u][v] + g1[u][am] + dp3[k][i][i][i]);
                        // printf("ndp[%d][%d] = %d\n", a+1, b+1, ndp[a][b]);
                        // printf("ndp[%d][%d] = %d\n", a+1, v+1, ndp[a][v]);
                        // printf("ndp[%d][%d] = %d\n", u+1, b+1, ndp[u][b]);
                    }
                }
            }

            REP(a, N) REP(b, N) dp[a][b] = ndp[a][b];
        }

        if(dp[0][0] >= INF) dp[0][0] = -1;
        cout << dp[0][0] << endl;
    }
    return 0;
}

/* vim:set foldmethod=marker: */

Measured memory_bytes: 2112