#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
ll n,m,c;
ll v,w,t;
ll arr[105][105];
ll pro[105][105];
ll buy[105][1069];
ll sell[105][1069];
ll grph[105][105];
bool works(ll x) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
grph[i][j]=pro[i][j]-x*arr[i][j];
}
grph[i][i]=LLONG_MIN/2;
}
for (ll k = 0; k < n; k++) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
grph[i][j]=max(grph[i][j],grph[i][k]+grph[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
if (grph[i][i]>=0) {
return true;
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
for (ll i = 0; i < 105; i++) {
for (ll j = 0; j < 105; j++) {
arr[i][j]=LLONG_MAX/2;
}
arr[i][i]=0;
}
cin>>n>>m>>c;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < c; j++) {
cin>>buy[i][j]>>sell[i][j];
}
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
for (ll k = 0; k < c; k++) {
if (buy[i][k]!=-1&&sell[j][k]!=-1) {
pro[i][j]=max(pro[i][j],sell[j][k]-buy[i][k]);
}
}
}
}
for (ll i = 0; i < m; i++) {
cin>>v>>w>>t;
v--;w--;
arr[v][w]=t;
}
for (ll k = 0; k < n; k++) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
}
}
}
ll s=0, e=1000000069;
while (s+1!=e) {
(works((s+e)/2)?s:e)=(s+e)/2;
}
cout<<s<<endl;
return 0;
}
