#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end()
#define sz(x) (int)(x.size())
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
struct E{
ll u , v , w ;
};
const ll maxn = 103 , maxk = 1e3 + 4 , inf = 1e16 + 7 ;
ll n , m , k ;
ll s[maxn][maxn] , b[maxn][maxn] ;
ll c[maxn][maxn] , d[maxn][maxn];
vector<pll> adj[maxn] ;
vector<E> edge ;
ll dp[maxn] ;
bool get(ll ans){
edge.clear() ;
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < n ; j++){
if (i == j) continue ;
E e ;
e.u = i , e.v = j , e.w = ((ans * d[i][j]) - c[i][j]) ;
edge.ps(e) ;
}
}
for (int i = 0; i < n; i++)
dp[i] = inf ;
dp[0] = 0 ;
for (int cnt = 0; cnt < n ; cnt ++){
for (E e : edge){
ll u = e.u , v = e.v , w = e.w ;
dp[v] = min(dp[v] , (dp[u] + w)) ;
}
}
bool check = false ;
for (E e : edge){
ll u = e.u , v = e.v , w = e.w ;
if (dp[v] > (dp[u] + w)){
check = true ;
break ;
}
}
return check ;
}
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(NULL) ;
cout.tie(NULL) ;
cin >> n >> m >> k ;
for (int i = 0 ; i < n; i++){
for (int j = 0 ; j < k ; j++){
ll ss , bb ;
cin >> bb >> ss ;
if (ss == -1) ss = 0-inf ;
if (bb == -1) bb = inf ;
s[i][j] = ss ; b[i][j] = bb ;
}
}
for (int i = 0 ; i < m ; i++){
ll u , v , t ;
cin >> u >> v >> t ;
u-- , v-- ;
adj[u].ps(mp(v , t)) ;
}
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < n ; j++){
for (int h = 0 ;h < k; h++){
c[i][j] = max(c[i][j] , (s[j][h] - b[i][h])) ;
}
}
}
for (int i = 0 ; i < n ; i++){
for (pii j : adj[i]){
d[i][j.first] = j.second ;
}
}
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < n ; j++){
if (!d[i][j])
d[i][j] = inf ;
}
}
for (int cnt = 0; cnt < n ; cnt ++){
for (int i = 0 ; i < n; i++){
for (int j = 0 ;j <= n ; j++)
d[i][j] = min(d[i][j] , (d[i][cnt] + d[cnt][j])) ;
}
}
ll l = 0 , r = 1e13 ;
while (l < r-1){
ll mid = (l + r) >> 1 ;
if (get(mid)){
l = mid + 1 ;
}
else
r = mid + 1 ;
}
cout << l << '\n' ;
}
