#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 107
using namespace std;
const long long inf=1e9;
int n,m,k,a,b,c,s[MAXN][2007],cost[MAXN][MAXN];
long long dist[MAXN][MAXN];
long long dp[MAXN][MAXN][MAXN];
void precalc(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
if(dist[i][k]+dist[k][f]<dist[i][f])dist[i][f]=dist[i][k]+dist[k][f];
}
}
}
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
cost[i][f]=0;
for(int t=1;t<=2*k;t+=2){
if(s[i][t]==-1 or s[f][t+1]==-1)continue;
cost[i][f]=max(cost[i][f],-s[i][t]+s[f][t+1]);
}
}
}
}
bool ok(long long x){
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
dp[i][f][1]=-inf;
for(int p=1;p<=n;p++){
if(cost[i][p]==0)continue;
dp[i][f][1]=max(dp[i][f][1],cost[i][p]-(dist[i][p]+dist[p][f])*x);
}
}
}
for(int w=2;w<=n;w++){
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
dp[i][f][w]=-inf;
/*for(int p=1;p<=n;p++){
dp[i][f][w]=max(dp[i][f][w],dp[i][p][w-1]+dp[p][f][1]);
}*/
}
if(dp[i][i][w]>=0)return true;
}
}
return false;
}
int bin(){
int l=0,r=inf+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(ok(tt)){
l=tt;
}else{
r=tt;
}
}
return l;
}
void check(){
for(int i=1;i<=n;i++){
for(int f=i+1;f<=n;f++){
if(dist[i][f]+dist[f][i]<inf)return;
}
}
cout<<"-1\n";
exit(0);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int f=1;f<=2*k;f++){
cin>>s[i][f];
}
}
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
dist[i][f]=inf;
}
dist[i][i]=0;
}
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
dist[a][b]=c;
}
precalc();
check();
cout<<bin()<<"\n";
return 0;
}
