#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#define maxn 1122

#define maxm 555555

typedef long long ll;

using namespace std;

ll inf=~0U>>;

ll to[maxm],next[maxm],c[maxm],first[maxn],edge;

ll cow[maxn],hold[maxn],d[maxn],tag[maxn],TAG=;

ll Q[maxm],bot,top;

ll dis[maxn][maxn],f[maxn],g[maxn][maxn];

bool can[maxn];

ll n,m,sumcow,ans,s,t;

void _init()

{

    sumcow=;

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

        for (int j=; j<=n; j++) dis[i][j]=-;

}

void spfa(ll x)

{

    for (int i=; i<=n; i++) f[i]=inf;

    Q[bot=top=]=x,f[x]=;

    while (bot<=top)

    {

        ll cur=Q[bot++];

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

            if (dis[cur][i]!=- && f[cur]+dis[cur][i]<f[i])

            {

                Q[++top]=i;

                f[i]=f[cur]+dis[cur][i];

            }

    }

    for (int i=; i<=n; i++) g[x][i]=f[i];

}

void _input()

{

    ll U,V,W;

    for (int i=; i<=n; i++) scanf("%I64d%I64d",&cow[i],&hold[i]),sumcow+=cow[i];

    while (m--)

    {

        scanf("%I64d%I64d%I64d",&U,&V,&W);

        if (dis[U][V]==-) dis[U][V]=dis[V][U]=W;

            else if (W<dis[U][V]) dis[U][V]=dis[V][U]=W;

    }

    for (int i=; i<=n; i++) if (cow[i]>) spfa(i);

}

void addedge(ll U,ll V,ll W)

{

    edge++;

    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;

    edge++;

    to[edge]=U,c[edge]=,next[edge]=first[V],first[V]=edge;

}

bool bfs()

{

    Q[bot=top=]=t,d[t]=,tag[t]=++TAG;

    while (bot<=top)

    {

        ll cur=Q[bot++];

        for (int i=first[cur]; i!=-; i=next[i])

        {

            if (c[i^]> && tag[to[i]]!=TAG)

            {

                tag[to[i]]=TAG,Q[++top]=to[i];

                d[to[i]]=d[cur]+,can[to[i]]=false;

                if (to[i]==s) return true;

            }

        }

    }

    return false;

}

ll dfs(ll cur,ll num)

{

    if (cur==t) return num;

    ll tmp=num,k;

    for (int i=first[cur]; i!=-; i=next[i])

        if (c[i]> && d[to[i]]==d[cur]- && tag[to[i]]==TAG && !can[to[i]])

        {

            k=dfs(to[i],min(c[i],num));

            if (k) num-=k,c[i]-=k,c[i^]+=k;

            if (num==) break;

        }

    if (num) can[cur]=true;

    return tmp-num;

}

bool check(ll x)

{

    s=,t=*n+,edge=-,ans=;

    for (int i=s; i<=t; i++) first[i]=-;

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

    {

        if (cow[i]>)

        {

            addedge(s,i,cow[i]);

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

                if (g[i][j]<=x) addedge(i,j+n,cow[i]);

        }

        addedge(i+n,t,hold[i]);

    }

    while (bfs()) ans+=dfs(s,inf);

    return ans==sumcow;

}

int main()

{

    inf*=inf;

    while (scanf("%I64d%I64d",&n,&m)!=EOF)

    {

        _init();

        _input();

        if (!check(inf-))

        {

            puts("-1");

            continue;

        }

        ll l=,r=inf-,mid;

        while (l<r)

        {

            mid=l/+r/;

            if (l&r&) mid++;

            if (check(mid)) r=mid;

                else l=mid+;

        }

        printf("%I64d\n",l);

    }

    return ;

}