//In the name of GOD
#include <bits/stdc++.h>
using namespace std;
const long long maxN=1e2+5, maxK=1e3+5, inf=1e18;
long long n, m, k, b[maxN][maxK], s[maxN][maxK], dis[maxN][maxN], tmp[maxN][maxN], mx[maxN][maxN];
bool can(long long x){
for (long long u=1; u<=n; u++)
for (long long v=1; v<=n; v++)
tmp[u][v]=(dis[u][v]!=inf ? x*dis[u][v] : x*inf)-mx[u][v];
for (long long w=1; w<=n; w++)
for (long long u=1; u<=n; u++)
for (long long v=1; v<=n; v++)
tmp[u][v]=min(tmp[u][v], tmp[u][w]+tmp[w][v]);
for (long long v=1; v<=n; v++)
if(tmp[v][v]<=0) return true;
return false;
}
int main(){
cin >>n >>m >>k;
for (long long v=1; v<=n; v++){
for (long long i=1; i<=k; i++)
cin >>b[v][i] >>s[v][i];
for (long long u=1; u<=n; u++)
dis[u][v]=inf;
}
for (long long i=1, u, v, w; i<=m; i++){
cin >>u >>v >>w;
dis[u][v]=w;
}
for (long long w=1; w<=n; w++)
for (long long u=1; u<=n; u++)
for (long long v=1; v<=n; v++)
dis[u][v]=min(dis[u][v], dis[u][w]+dis[w][v]);
for (long long u=1; u<=n; u++){
for (long long v=1; v<=n; v++){
mx[u][v]=-inf;
for (long long i=1; i<=k and dis[u][v]!=inf; i++)
if(b[u][i]!=-1 and s[v][i]!=-1)
mx[u][v]=max(mx[u][v], s[v][i]-b[u][i]);
}
}
long long l=0, r=inf;
while(r-l>1){
long long mid=(r+l)>>1;
if(can(mid)) l=mid;
else r=mid;
}
cout <<l;
}
