#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>
const int siz = 101;
const int MK = 1001;
ll dis[siz][siz];
ll pro[siz][siz];
ll pr[siz][2*MK];
int main()
{
int n, m, K;
cin >> n >> m >> K;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j)dis[i][j] = 1e18;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2 * K; j++) {
cin >> pr[i][j];
if (pr[i][j] == -1) {
if (j % 2)pr[i][j] = -1e18;
else pr[i][j] = 1e18;
}
}
}
for (int i = 0; i < m; i++) {
ll a, b, c;
cin >> a >> b >> c;
a--, b--;
dis[a][b] = min(dis[a][b],c);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 2*K; k+=2) {
pro[i][j] = max(pro[i][j], -pr[i][k] + pr[j][k + 1]);
}
}
}
int l = 0, r=1e9;
while (l < r) {
int mid = (l + r+1) / 2;
// is it possible that profit/dis >= mid <--> mid*dis - profit <= 0?
vector<vll> procur(n, vll(n,1e18));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
procur[i][j] = min(procur[i][j], mid * (dis[i][k] + dis[k][j]) - pro[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i!=j)procur[i][j] = 200 * procur[i][j] - 1;
}
}
vll dp(n,1e18);
dp[0] = 0;
bool f = 0;
for (int it = 0; it <= n; it++) {
vll dpt= dp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (it == n && dpt[i] > dp[j] + procur[j][i])f = 1;
dpt[i] = min(dpt[i], dp[j] + procur[j][i]);
}
}
dp = dpt;
}
if (f == 1) {
l = mid;
}
else {
r = mid-1;
}
}
cout << l;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
