#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}

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

int main(){
    int n,m;
    while(1){
        cin >> n >> m;
        if(n==0)break;
        vector<int>h(n);
        map<int,int> ss;
        vector<int> num(n);
        vector<int> c(n);
        rep(i,n-2){
            cin >> c[i+1] >> h[i+1];
            num[i+1] = ss[h[i+1]];
            ss[h[i+1]]++;
        }
        rep(i,n)rep(j,n)rep(k,1<<10)dp[i][j][k] = inf;
        h[0] = 0;
        h[n-1] = 1000;
        vector<vector<pii> > gu(n);
        vector<vector<pii> > gd(n);
        vector<vector<pii> > u(n);
        vector<vector<pii> > d(n);
        rep(i,m){
            int a,b,e;
            cin >> a >> b >> e;
            a--;b--;
            if(h[a]==h[b]){
                gu[a].push_back(MP(b,e));
                gd[b].push_back(MP(a,e));
                u[a].push_back(MP(b,e));
                d[b].push_back(MP(a,e));
            }else if(h[a]<h[b]){
                u[a].push_back(MP(b,e));
            }else{
                d[b].push_back(MP(a,e));
            }
        }
        priority_queue<pair<pii,pair<int,int>>,vector<pair<pair<int,int>,pii>>,greater<pair<pair<int,int>,pii>> >pq;
        dp[0][0][1] = 0;
        pq.push(MP(MP(0,1),MP(0,0)));
        while(!pq.empty()){
            auto x = pq.top();
            pq.pop();
            int a = x.second.first;
            int b = x.second.second;
            int cost = x.first.first;
            int reach = x.first.second;
            if(dp[a][b][reach]!=cost)continue;
            // cerr << a << " " << b << " " << cost << " " << reach << endl;
            if(h[a]<=h[b]){
                for(auto x:u[a]){
                    int nxt = x.first;
                    int dd = cost + x.second;
                    int nxtreach = reach;
                    if(h[nxt]<h[b]){
                        dd += c[nxt];
                        if(chmin(dp[nxt][b][nxtreach],dd)){
                            pq.push(MP(MP(dp[nxt][b][nxtreach],nxtreach),MP(nxt,b)));
                        }
                    }else if(h[nxt]>h[b]){
                        dd += c[nxt];
                        nxtreach = (1<<num[nxt]);
                        if(chmin(dp[nxt][b][nxtreach],dd)){
                            pq.push(MP(MP(dp[nxt][b][nxtreach],nxtreach),MP(nxt,b)));
                        }
                    }else{
                        if(nxt!=b){
                            dd += c[nxt];
                            nxtreach = reach|(1<<num[nxt]);
                        }
                        if(chmin(dp[nxt][b][nxtreach],dd)){
                            pq.push(MP(MP(dp[nxt][b][nxtreach],nxtreach),MP(nxt,b)));
                        }
                    }
                }
            }
            if(h[b]<=h[a]){
                for(auto x:d[b]){
                    int nxt = x.first;
                    int dd = cost + x.second;
                    int nxtreach = reach;
                    if(h[nxt]<h[a]){
                        dd += c[nxt];
                        if(chmin(dp[a][nxt][nxtreach],dd)){
                            pq.push(MP(MP(dp[a][nxt][nxtreach],nxtreach),MP(a,nxt)));
                        }
                    }else if(h[nxt]>h[a]){
                        dd += c[nxt];
                        nxtreach = (1<<num[nxt]);
                        if(chmin(dp[a][nxt][nxtreach],dd)){
                            pq.push(MP(MP(dp[a][nxt][nxtreach],nxtreach),MP(a,nxt)));
                        }
                    }else{
                        if(nxt!=a){
                            dd += c[nxt];
                            nxtreach = reach|(1<<num[nxt]);
                        }
                        if(chmin(dp[a][nxt][nxtreach],dd)){
                            pq.push(MP(MP(dp[a][nxt][nxtreach],nxtreach),MP(a,nxt)));
                        }
                    }
                }
            }
            if(h[a]==h[b]){
                for(auto x:gu[a]){
                    int nxt = x.first;
                    int dd = cost + x.second;
                    int nxtreach = reach;
                    
                    if(((reach>>num[nxt])&1)==0){
                        dd += c[nxt];
                        nxtreach = reach|(1<<num[nxt]);
                    }
                    if(chmin(dp[nxt][b][nxtreach],dd)){
                        pq.push(MP(MP(dp[nxt][b][nxtreach],nxtreach),MP(nxt,b)));
                    }
                    
                }
                for(auto x:gd[b]){
                    int nxt = x.first;
                    int dd = cost + x.second;
                    int nxtreach = reach;
                    
                    if(((reach>>num[nxt])&1)==0){
                        dd += c[nxt];
                        nxtreach = reach|(1<<num[nxt]);
                    }
                    if(chmin(dp[a][nxt][nxtreach],dd)){
                        pq.push(MP(MP(dp[a][nxt][nxtreach],nxtreach),MP(a,nxt)));
                    }
                    
                }
            }
        }
        if(dp[n-1][n-1][1]==inf){
            cout << -1 << endl;
        }else{
            cout << dp[n-1][n-1][1] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 15108