/**

题目：poj2391 Ombrophobic Bovines

链接：http://poj.org/problem?id=2391

题意：有n块区域，第i块区域有ai头奶牛，以及一个可以容纳bi头奶牛的棚子。n块区域由m条可以容纳无数奶牛经过的双向通道相连，给定奶牛通过通道的时间。

问所有奶牛回到棚子需要的最短时间。

思路：。。。我好菜哦。没想到，看了blog才知道怎么做。

先用floyd求得两块区域相通最短时间。

将点x拆分成x,x'。源点s连接x，容量为x的奶牛数。x'连接汇点t容量为x的棚子容纳数。

二分一个时间time，表示需要的最短时间。无论奶牛在哪个地方，只要从该点出发，距离time以内的点都可以到达。

所以如果x点到y点的最短时间<=time。那么x连接y'，容量为INF。

对这个二分图求最大流。如果最大流=总奶牛数量。那么表示该时间内可行。

注意时间！超int。

*/

#include<iostream>

#include<cstring>

#include<vector>

#include<map>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const long long MAS = 1e13;

const int INF = 0x3f3f3f3f;

typedef long long LL;

const int N = ;///

struct Edge{

    int from, to, cap, flow;

    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}

};

struct Dinic{

    int n, m, s, t;

    vector<Edge> edges;

    vector<int> G[N];

    bool vis[N];

    int d[N];

    int cur[N];

    void init(int n)

    {

        this->n = n;

        for(int i = ; i <= n; i++) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int cap)

    {

        edges.push_back(Edge(from,to,cap,));

        edges.push_back(Edge(to,from,,));

        m = edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    bool BFS()

    {

        memset(vis, , sizeof vis);

        queue<int> Q;

        Q.push(s);

        d[s] = ;

        vis[s] = ;

        while(!Q.empty())

        {

            int x = Q.front();

            Q.pop();

            for(int i = ; i < G[x].size(); i++)

            {

                Edge &e = edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow)

                {

                    vis[e.to] = ;

                    d[e.to] = d[x]+;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x,int a)

    {

        if(x==t||a==) return a;

        int flow = , f;

        for(int &i = cur[x]; i < G[x].size(); i++)

        {

            Edge& e = edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

            {

                e.flow += f;

                edges[G[x][i]^].flow -= f;

                flow += f;

                a -= f;

                if(a==) break;

            }

        }

        return flow;

    }

    int Maxflow(int s,int t)

    {

        this->s = s, this->t = t;

        int flow = ;

        while(BFS())

        {

            memset(cur, , sizeof cur);

            flow += DFS(s,INF);

        }

        return flow;

    }

};

LL f[N][N];

void floyd(int n)

{

    for(int k = ; k <= n; k++){

        for(int i = ; i <= n; i++){

            for(int j = ; j <= n; j++){

                f[i][j] = min(f[i][j],f[i][k]+f[k][j]);

            }

        }

    }

}

int main()

{

    int n, m, sum;

    while(scanf("%d%d",&n,&m)==)

    {

        int s = , t = n*+;

        Dinic dinic;

        dinic.init(t);

        sum = ;

        int flow, cap;

        for(int i = ; i <= n; i++){

            scanf("%d%d",&flow,&cap);

            sum += flow;

            dinic.AddEdge(s,i,flow);

            dinic.AddEdge(i+n,t,cap);

            dinic.AddEdge(i,i+n,INF);

        }

        int u, v;

        LL time;

        for(int i = ; i <= n ; i++)

            for(int j = ; j <= n; j++)

                f[i][j] = MAS;

        for(int i = ; i <= m; i++){

            scanf("%d%d%lld",&u,&v,&time);

            f[u][v] = min(f[u][v],time);

            f[v][u] = f[u][v];

        }

        floyd(n);

        Dinic Save = dinic;

        LL lo = , hi = MAS, mid;

        while(lo<hi){

            mid = (lo+hi)/;

            dinic = Save;

            for(int i = ; i <= n; i++){

                for(int j = ; j <= n; j++){

                    if(f[i][j]<=mid){

                        dinic.AddEdge(i,j+n,INF);

                    }

                }

            }

            int masflow = dinic.Maxflow(s,t);

            if(masflow==sum){

                hi = mid;

            }else

            {

                lo = mid+;

            }

        }

        if(hi==MAS){

            printf("-1\n");

        }else

        {

            printf("%lld\n",hi);

        }

    }

    return ;

}