#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
vector<vector<int> > t, p, graph;
vector<vector<pii> > vect;
int32_t main(){
int n, m, k, a, b, c;
cin>>n>>m>>k;
vect.resize(n+1, vector<pii>(k));
graph.resize(n+1, vector<int>(n+1));
t.resize(n+1, vector<int>(n+1, LLONG_MAX/2));
p.resize(n+1, vector<int>(n+1, 0));
for (int i=1; i<=n; ++i)for (int j=0; j<k; ++j)cin>>vect[i][j].fi>>vect[i][j].se;
while (m--){
cin>>a>>b>>c;
t[a][b]=min(t[a][b], c);
}
for (int l=1; l<=n; ++l)for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)t[i][j]=min(t[i][j], t[i][l]+t[l][j]);
for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)for (int l=0; l<k; ++l)if (vect[i][l].fi!=-1&&vect[j][l].se!=-1)p[i][j]=max(p[i][j], vect[j][l].se-vect[i][l].fi);
int low=0, high=1e9;
while (low+1<high){
int mid=(low+high)/2;
for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)graph[i][j]=p[i][j]-mid*min((LLONG_MAX/2)/mid, t[i][j]);
for (int l=1; l<=n; ++l)for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)graph[i][j]=max(graph[i][j], graph[i][l]+graph[l][j]);
bool can=0;
for (int i=1; i<=n; ++i)if (graph[i][i]>=0)can=1;
if (can)low=mid;
else high=mid;
}
cout<<low;
}
