#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define int long long
const int N = 105, inf = 1e17;
int d[N][N], d2[N][N], b[N][N * 10], s[N][N * 10], prf[N][N];
signed main(){
int n, m, K;
cin>>n>>m>>K;
for (int i=1;i<=n;i++){
for (int j=1;j<=K;j++)
cin>>b[i][j]>>s[i][j];
}
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (i == j)
continue;
d[i][j] = 1e17;
for (int k=1;k<=K;k++)
if (min(b[i][k], s[j][k]) != -1)
prf[i][j] = max(prf[i][j], - b[i][k] + s[j][k]);
}
}
for (int i=1, a, b, c;i<=m;i++){
cin>>a>>b>>c;
d[a][b] = c;
}
for (int k=1;k<=n;k++){
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int l = 0, r = 1e9 + 7;
while (l + 1 < r){
int mid = (l + r) / 2;
// mid = 3;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (i == j)
d2[i][j] = -inf;
else
d2[i][j] = prf[i][j] - min(mid, inf / d[i][j] + 1) * d[i][j];
}
}
for (int k=1;k<=n;k++){
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
d2[i][j] = max(d2[i][j], d2[i][k] + d2[k][j]);
}
bool t = 0;
for (int i=1;i<=n;i++)
t |= d2[i][i] >= 0;
if (t)
l = mid;
else
r = mid;
}
cout<<l<<'\n';
}
