#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 107;
const ll INF = 1e18 + 7;
int n, m, kk;
ll b[MAXN][1007], s[MAXN][1007];
ll graph[MAXN][MAXN], adj[MAXN][MAXN], profit[MAXN][MAXN];
void shortest_path(ll dis[MAXN][MAXN]){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++)
dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
}
}
}
int main(){
cin >> n >> m >> kk;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= kk; j++)
cin >> b[i][j] >> s[i][j];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
graph[i][j] = INF;
}
for(int i = 1; i <= m; i++){
int x, y, z;
cin >> x >> y >> z;
graph[x][y] = z;
}
shortest_path(graph);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= kk; k++){
if(s[j][k] != -1 && b[i][k] != -1){
profit[i][j] = max(profit[i][j], s[j][k] - b[i][k]);
}
}
}
}
ll lef = 1, rig = 1e9;
while(lef <= rig){
ll mid = (lef + rig)/2;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
adj[i][j] = mid*min(graph[i][j], INF/mid) - profit[i][j];
}
shortest_path(adj);
bool check = 0;
for(int i = 1; i <= n; i++){
if(adj[i][i] <= 0)
check = 1;
}
if(check)
lef = mid + 1;
else
rig = mid - 1;
}
cout << rig << endl;
return 0;
}
