#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #include <queue>

 using namespace std;

 #define next Next

 const int inf = 0x3f3f3f3f;

 const int maxn=;

 int level[maxn];

 int iter[maxn];

 int head[maxn],tot;

 struct edge{

     int to,cap,Next;

 } e[]; ///此处应为边的两倍，加一条容量为0的反向边

 void init(){

     memset(head,-,sizeof(head));

     tot=;

 }

 void add(int from,int to,int cap){

     e[tot].Next=head[from];

     e[tot].to=to;

     e[tot].cap=cap;

     head[from]=tot;

     tot++;

 }

 void addedge(int from,int to,int cap){

     add(from,to,cap);

     add(to,from,);

 }

 void bfs(int s){

     memset(level,-,sizeof(level));

     queue<int> q;

     level[s]=;

     q.push(s);

     while(!q.empty()){

         int v=q.front(); q.pop();

         for(int i=head[v];~i;i=e[i].Next){

             edge &ed=e[i];

             if(ed.cap>&&level[ed.to]<){

                 level[ed.to]=level[v]+;

                 q.push(ed.to);

             }

         }

     }

 }

 int dfs(int v,int t,int f){

     if(v==t) return f;

     for(int &i=iter[v];~i;i=e[i].Next){

         edge &ed=e[i];

         if(ed.cap>&&level[v]<level[ed.to]){

             int d=dfs(ed.to,t,min(f,ed.cap));

             if(d>){

                 ed.cap-=d;

                 e[i^].cap+=d;

                 return d;

             }

         }

     }

     return ;

 }

 int max_flow(int s,int t){

     int flow=;

     while(){

         bfs(s);

         if(level[t]<) return flow;

         memcpy(iter,head,sizeof(iter));

         int f;

         while((f=dfs(s,t,inf))>){

             flow+=f;

         }

     }

 }

 int niu[maxn],capacity[maxn];

 typedef long long ll;

 ll dp[maxn][maxn];

 void floyd(int n)

 {

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

     {

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

         {

             //if(i==j) continue;

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

             {

                 if(i==k||j==k||i==j) continue;

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

             }

         }

     }

 }

 int f,p;

 void cons(ll T,int s,int t)

 {

     init();

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

     {

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

         addedge(i,i+f,inf);

         addedge(i+f,t,capacity[i]);

     }

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

     {

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

         {

             if(i==j) continue;

             if(dp[i][j]<=T)

             {

                 addedge(i,j+f,inf);

             }

         }

     }

 }

 int main()

 {

     int sum = ;

     scanf("%d %d",&f,&p);

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

     {

         scanf("%d %d",&niu[i],&capacity[i]);

         sum += niu[i];

     }

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

     {

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

         {

             dp[i][j] = 1e15;

         }

     }

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

     {

         int x,y;

         ll w;

         scanf("%d %d %lld",&x,&y,&w);

         dp[x][y] = min(dp[x][y],w);   ///一定要注意两点之间的有多条边的情况

         dp[y][x] = dp[x][y];

     }

     floyd(f);

     ll l = ,r = 2000000000000LL;

     ll mid = ;

     int s,t;

     s = ,t = ; ///s,t一定要在head数组范围内

     int flow = ;

     ll ans = ;

     while(l<=r)

     {

         mid = (l+r)/2LL;

         cons(mid,s,t);

         flow = max_flow(s,t);

        // printf("%lld %d\n",mid,flow);

         if(flow==sum)

         {

             ans = mid;

             r = mid-;

         }

         else

         {

             l = mid+;

         }

     }

     if(ans==)

     {

         puts("-1");

     }

     else

     {

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

     }

     return ;

 }

 /*

 3 4

 7 2

 0 4

 2 6

 1 2 40

 1 2 70

 1 2 90

 1 2 120

 */