#include <bits/stdc++.h>
using namespace std;
const int N=101,K=1001;
const long long INF=LLONG_MAX/2;
long long dp[N][N],s[N][K],b[N][K],timp[N][N],sol[N][N];
int n,m,k;
void citeste()
{
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
timp[i][j]=INF;
}
for(int j=1; j<=k; j++)
{
cin>>b[i][j]>>s[i][j];
}
}
for(int i=1; i<=m; i++)
{
int a,b;
long long c;
cin>>a>>b>>c;
timp[a][b]=c;
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
timp[i][j]=min(timp[i][j],timp[i][k]+timp[k][j]);
}
}
for(int t=1; t<=k; t++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(b[i][t]!=-1&&s[j][t]!=-1)
{
dp[i][j]=max(dp[i][j],s[j][t]-b[i][t]);
}
}
}
}
long long st=0,dr=1e9,ans=0;
while(st<=dr)
{
long long mid=(st+dr)/2;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
sol[i][j]=-mid*min(timp[i][j],INF/mid)+dp[i][j];
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
sol[i][j]=max(sol[i][j],sol[i][k]+sol[k][j]);
}
}
}
bool da=false;
for(int i=1; i<=n; i++)
{
if(sol[i][i]>=0)
da=true;
}
if(da)
{
ans=mid;
st=mid+1;
}
else
{
dr=mid-1;
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
citeste();
return 0;
}
