#include<bits/stdc++.h>
using namespace std;

using Weight=int;
enum{ASC,DES,SAME0,SAME1};
struct Edge{
    int to;
    Weight w;
};
using Edges=vector<Edge>;
using Graph=vector<Edges>;

const Weight INF=1e9;
Weight dijkstra(int s,int t,Graph& g){
    vector<Weight> d(g.size(),INF);
    d[s]=0;
    priority_queue<pair<Weight,int>,vector<pair<Weight,int>>,greater<>> que;
    vector<int> used(g.size(),false);
    que.push(make_pair(Weight(0),s));
    while(!que.empty()){
        auto ret=que.top(); que.pop();
        int v=ret.second;
        if(v==t) return ret.first;
        if(used[v]) continue;
        used[v]=true;
        for(int i=0;i<g[v].size();i++){
            int to=g[v][i].to;
            Weight w=g[v][i].w+d[v];
            if(w<d[to] && !used[to]){
                d[to]=w;
                que.push(make_pair(w,to));
            }
        }
    }
    return INF;
}

int vertex(int x,int y,int mask){
    return (x<<23)+(y<<12)+mask;
}
Weight solve(int n,int m,vector<Weight>& d,vector<int> &e,Graph& g,vector<vector<int>> &label){
    map<int,vector<int>> em;
    for(int i=0;i<n;i++) em[e[i]].push_back(i);
    vector<int> posm(n);
    for(auto &e:em){
        for(int i=0;i<e.second.size();i++){
            posm[e.second[i]]=i;
        }
    }
    int index=0;
    Graph graph;
    map<int,int> vmap;
    auto getIndex=[&](int v){
        if(!vmap.count(v)){
            graph.push_back(Edges());
            return vmap[v]=index++;
        }  
        else{
            return vmap[v];
        }
    };
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            int upper=(e[i]==e[j] ? (1<<(em[e[i]].size())) : 1);
            for(int mask=0;mask<upper;++mask){
                int v=getIndex(vertex(i,j,mask));
                if(e[i]==e[j] && mask!=0){
                    int to=getIndex(vertex(i,j,0));
                    graph[v].push_back(Edge{to,0});
                }
                if(e[i]==e[j]){
                    if(!(mask & (1<<posm[i]))){
                        int to=getIndex(vertex(i,j,mask|(1<<posm[i])));
                        graph[v].push_back(Edge{to,0});
                        if(mask!=0) continue;
                    }
                    if(!(mask & (1<<posm[j]))){
                        int to=getIndex(vertex(i,j,mask|(1<<posm[j])));
                        graph[v].push_back(Edge{to,0});
                        if(mask!=0) continue;
                    }
                }
                for(int k=0;k<g[i].size();k++){
                    if(label[i][k]==DES||label[i][k]==SAME1) continue;
                    if(label[i][k]==ASC && mask!=0) continue;
                    int w=g[i][k].w+d[g[i][k].to];
                    if(((1<<posm[g[i][k].to]) & mask)|| g[i][k].to==j){
                        w-=d[g[i][k].to];
                    }
                    int to=getIndex(vertex(g[i][k].to,j,mask));
                    graph[v].push_back(Edge{to,w});
                }
                for(int k=0;k<g[j].size();k++){
                    if(label[j][k]==ASC||label[j][k]==SAME0) continue;
                    if(label[j][k]==DES && mask!=0) continue;
                    int w=g[j][k].w+d[g[j][k].to];
                    if(((1<<posm[g[j][k].to]) & mask)|| g[j][k].to==i){
                        w-=d[g[j][k].to];
    
                    }
                    int to=getIndex(vertex(i,g[j][k].to,mask));
                    
                    graph[v].push_back(Edge{to,w});
                }
                
            }
        }
    }
    
    return dijkstra(getIndex(vertex(0,0,0)),getIndex(vertex(n-1,n-1,0)),graph);
}
int main(){
    int n,m;
    while(cin>>n>>m,n){
        vector<Weight> d(n);
        vector<int> e(n);
        d[0]=e[0]=0;
        for(int i=0;i<n-2;i++){
            cin>>d[i+1]>>e[i+1];
        }
        d[n-1]=0;
        e[n-1]=1000;
        vector<vector<int>> label(n);
        Graph g(n);
        for(int i=0;i<m;i++){
            int a,b;
            Weight c;
            cin>>a>>b>>c;
            --a,--b;
            if(e[a]<e[b]){
                g[a].push_back(Edge{b,c});
                label[a].push_back(ASC);
            }
            if(e[a]>e[b]){
                g[b].push_back(Edge{a,c});
                label[b].push_back(DES);
            }
            if(e[a]==e[b]){
                g[a].push_back(Edge{b,c});
                label[a].push_back(SAME0);
                g[b].push_back(Edge{a,c});
                label[b].push_back(SAME1);
            }
        }
        
        auto ret=solve(n,m,d,e,g,label);
        cout<<(ret>=INF ? Weight(-1) : ret)<<endl;
    }
    return 0;
}


Measured memory_bytes: 80184