#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const ll N=100,inf=1e18;
ll n,m,k;
ll dist[N][N],profit[N][N],adj[N][N],adj2[N][N];
bool check(ll x){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
if(dist[i][j]==inf){
adj[i][j]=-inf;
}
else{
adj[i][j]=max(profit[i][j]-dist[i][j]*x,-inf);
}
}
adj[i][i]=-inf;
}
ll res=-inf;
for(ll r=0;r<n;r++){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
adj[i][j]=max(adj[i][j],adj[i][r]+adj[r][j]);
res=max(res,adj[i][i]);
if(res>=0){
return true;
}
adj[i][j]=min(adj[i][j],inf);
adj2[i][j]=adj[i][j];
}
}
}
for(ll r=0;r<n;r++){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
adj2[i][j]=max(adj2[i][j],adj2[i][r]+adj2[r][j]);
if(adj2[i][j]>adj[i][j]){
return true;
}
}
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>k;
ll b[n][k],s[n][k];
for(ll i=0;i<n;i++){
for(ll j=0;j<k;j++){
cin>>b[i][j]>>s[i][j];
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
dist[i][j]=inf;
}
dist[i][i]=0;
}
for(ll i=0;i<m;i++){
ll u,v,t;
cin>>u>>v>>t;
u--,v--;
dist[u][v]=t;
}
for(ll r=0;r<n;r++){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
dist[i][j]=min(dist[i][j],dist[i][r]+dist[r][j]);
}
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
profit[i][j]=0;
for(ll c=0;c<k;c++){
if(s[j][c]>-1&&b[i][c]>-1){
profit[i][j]=max(profit[i][j],s[j][c]-b[i][c]);
}
}
}
}
ll l=0,r=1e9+1;
while(l<r){
ll mid=(l+r+1)/2;
if(check(mid)==true){
l=mid;
}
else{
r=mid-1;
}
}
cout<<l;
}
