//Khoda Hast :)//
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ret(x) return cout << x << endl, 0;
#define all(x) x.begin(),x.end()
#define pf push_front
#define ff pop_front
#define pb push_back
#define bb pop_back
#define F first
#define S second
using namespace std;
const int N = 200, M = 1e4, T = 1e3 + 10, OO = 1e9;
int a[N][T], b[N][T], l[N][N], p[N][N], n, m, t;
long long d[N][N];
vector<int> adj[N];
bool check(int x)
{
bool is = false;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
d[i][j] = 1ll * l[i][j] * x - 1ll * p[i][j];
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
if(i == j && d[i][k] + d[k][j] <= 0)
is = true;
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
return is;
}
int main()
{
ios;
cin >> n >> m >> t;
for(int i = 0; i < n; i++)
for(int j = 0; j < t; j++)
cin >> a[i][j] >> b[i][j];
for(int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
u--, v--;
adj[u].pb(v);
adj[v].pb(u);
d[u][v] = w;
d[v][u] = w;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(i != j && !d[i][j])
d[i][j] = 1ll * OO;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
p[i][j] = -OO;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
l[i][j] = OO;
for(int i = 0; i < n; i++)
{
l[i][i] = 0;
for(auto j : adj[i])
l[i][j] = d[i][j];
}
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
l[i][j] = min(l[i][j], l[i][k] + l[k][j]);
for(int i = 0; i < n; i++)
adj[i].clear();
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
bool is = false;
for(int k = 0; k < t; k++)
if(a[i][k] != -1 && b[j][k] != -1)
p[i][j] = max(p[i][j], b[j][k] - a[i][k]), is = true;
if(is)
adj[i].pb(j);
}
int lft = 0, rgt = OO;
while(lft + 1 < rgt)
{
int mid = (lft + rgt) / 2;
if(check(mid))
lft = mid;
else
rgt = mid;
}
cout << lft << endl;
return 0;
}
