#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=105;
const int M=10005;
const int INF=1.05e9;
const int mod=1e9+7;
int n,m,k;
vector<int> v[N];
vector<int> a(M),b(M),c(M);
int chmin(int &a,int b){
if(a>b){
a=b;return 1;
}
return 0;
}
int solve(int t){
vector dis(2,vector<int>(N,0));
int flag=0;
for(int i=0;i<n;i++){
flag=0;
for(int j=0;j<m;j++){
flag|=chmin(dis[0][b[j]],dis[0][a[j]]+c[j]*t);
flag|=chmin(dis[0][a[j]],dis[0][b[j]]+c[j]*t);
flag|=chmin(dis[1][b[j]],dis[1][a[j]]+c[j]*t);
flag|=chmin(dis[1][a[j]],dis[1][b[j]]+c[j]*t);
if(v[a[j]][0]!=-1){
flag|=chmin(dis[0][a[j]],dis[1][a[j]]-v[a[j]][1]);
flag|=chmin(dis[1][a[j]],dis[0][a[j]]+v[a[j]][0]);
}
if(v[b[j]][0]!=-1){
flag|=chmin(dis[0][b[j]],dis[1][b[j]]-v[b[j]][1]);
flag|=chmin(dis[1][b[j]],dis[0][b[j]]+v[b[j]][0]);
}
}
}
return flag;
}
int32_t main(){
abcorz;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=0;j<k*2;j++){
int p;cin>>p;
v[i].push_back(p);
}
}
for(int i=0;i<m;i++){
cin>>a[i]>>b[i]>>c[i];
}
int l=0,r=INF;
while(r-l>1){
int mid=(l+r)>>1;
if(solve(mid))l=mid;
else r=mid;
}
cout<<l<<endl;
return 0;
}
