Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,t;

#define MAXN 110

#define MAXK 1010

int b[MAXN][MAXK],s[MAXN][MAXK];

struct edges

{

	int u,v,w;

}es[MAXN * MAXN];

int tot = 0;

int d[MAXN][MAXN];

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt;

	long double v;

}e[MAXN * MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,long double c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

long double dis[MAXN];

bool v[MAXN];

bool SPFA(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dis[e[i].to] <= dis[k] + e[i].v)

		{

			if(v[e[i].to])return true;

			dis[e[i].to] = dis[k] + e[i].v;

			if(SPFA(e[i].to))return true;

		}

	}

	v[k] = false;

	return false;

}

bool check(long double k)

{

	memset(lin,0,sizeof(lin));edgenum = 0;

	for(int i = 1;i <= n;++i)dis[i] = -10000000000000000;

	memset(v,false,sizeof(v));

	for(int i = 1;i <= tot;++i)add(es[i].u,es[i].v,(long double)es[i].w - k * (long double)d[es[i].u][es[i].v]);

	for(int i = 1;i <= n;++i)if(SPFA(i))return true;

	return false;

}

int main()

{

	n = read();m = read();t = read();

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= t;++j)

			b[i][j] = read(),s[i][j] = read();

	memset(d,0x3f,sizeof(d));

	for(int i = 1;i <= m;++i)

	{

		int x = read(),y = read();

		d[x][y] = min(d[x][y],read());

	}

	for(int k = 1;k <= n;++k)

		for(int i = 1;i <= n;++i)

			for(int j = 1;j <= n;++j)

				d[i][j] = min(d[i][j],d[i][k] + d[k][j]);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			if(i == j)continue;

			if(d[i][j] == INF)continue;

			int maxval = 0;

			for(int k = 1;k <= t;++k)

			{

				if(s[j][k] != -1 && b[i][k] != -1)

					maxval = max(maxval,s[j][k] - b[i][k]);

			}

			++tot;

			es[tot].u = i;es[tot].v = j;es[tot].w = maxval;

		}

	}

	long double l = 0,r = 10000000000,mid;

	while(r - l > 1e-5)

	{

		mid = (l + r) * 0.5;

		if(check(mid))l = mid;

		else r = mid;

	}

	printf("%d\n",(int)(l + 1e-6));

	return 0;

}