def bellman_ford(n, m, k, markets, footpaths):
INF = float('inf')
dist = [0] + [-INF] * n # Initialize distances with -INF
for _ in range(n - 1): # Run Bellman-Ford algorithm
for u, v, w in footpaths:
if dist[u] != -INF and dist[u] + w > dist[v]:
dist[v] = dist[u] + w
max_efficiency = 0
for _ in range(n): # Iterate for each market as a starting point
for u, v, w in footpaths:
if dist[u] != -INF and dist[u] + w > dist[v]:
dist[v] = dist[u] + w
max_efficiency = max(max_efficiency, dist[v] // k)
return max_efficiency
# Input processing
n, m, k = map(int, input().split())
markets = [list(map(int, input().split())) for _ in range(n)]
footpaths = [tuple(map(int, input().split())) for _ in range(m)]
# Solve and print the result
result = bellman_ford(n, m, k, markets, footpaths)
print(result)
