#include <iostream>
using namespace std;
typedef long long ll;
const ll N = 1e2,K = 1e3;
const ll inf = 1e9;
ll b[N][K],s[N][K],d[N][N];
ll p[N][N];
int main(){
ll n,m,k,i,j,u,w,x,l;
cin>>n>>m>>k;
for(i = 0;i < n;i++){
for(j = 0;j < n;j++)d[i][j] = inf;
for(j = 0;j < k;j++){
cin>>b[i][j]>>s[i][j];
}
}
for(i = 0;i < m;i++){
cin>>u>>w>>x;w--;u--;
d[u][w] = x;
}
for(i = 0;i < n;i++){
for(j = 0;j < n;j++){
for(l = 0;l < n;l++){
d[j][l] = min(d[j][l],d[j][i] + d[i][l]);
}
}
}
ll lef = 0,r = inf;
while(lef != r){
ll mij = (lef + r + 1)/2;
for(i = 0;i < n;i++){
for(j = 0;j < n;j++){
p[i][j] = -d[i][j]*mij;
for(l= 0;l < k;l++){
if(b[i][l] == -1 || s[j][l] == -1)continue;
p[i][j] = max(p[i][j],-d[i][j]*mij + s[j][l] - b[i][l]);
}
}
}
for(i = 0;i < n;i++){
for(j = 0;j < n;j++){
for(l = 0;l < n;l++){
p[j][l] = max(p[j][l],p[j][i] + p[i][l]);
}
}
}
bool ok = 0;
for(i = 0;i < n;i++)if(p[i][i] >= 0){
ok = 1;
}
if(ok)lef = mij;
else r = mij - 1;
}
cout<<lef;
return 0;
}
