#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n, maxnights, h;
cin >> n >> maxnights >> h;
vector<ll> vis(n), depth(n, 1e8);
vector<vector<pair<ll, ll>>> adj(n), radj(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < h; j++) {
ll a, b;
cin >> a >> b;
adj[i].push_back({a, b});
radj[a].push_back({i, b});
}
}
auto dfs = [&](auto &&self, ll u) {
if (vis[u])
return;
vis[u] = 1;
for (auto [x, y] : radj[u]) {
if (vis[x])
continue;
self(self, x);
}
};
vector<ll> visd(n);
depth[0] = 0;
auto depthdfs = [&](auto &&self, ll u) {
if (vis[u] == 0)
return;
if (visd[u])
return;
visd[u] = 1;
for (auto [x, y] : adj[u]) {
if (visd[x])
continue;
depth[x] = min(depth[x], depth[u] + 1);
self(self, x);
}
};
vector<ll> ans;
auto dfs1 = [&](auto &&self, ll u, ll stay) {
if (u == n - 1) {
if (stay <= maxnights)
ans.push_back(stay);
return;
}
if (vis[u] == 0 or vis[u] == 2)
return;
vis[u] = 2;
for (auto [x, y] : adj[u]) {
if (!(vis[u] == 0 or vis[u] == 2 or depth[x] < depth[u])) {
self(self, x, stay + y);
}
}
vis[u] = 1;
};
depthdfs(depthdfs, 0);
dfs(dfs, n - 1);
dfs1(dfs1, 0, 0);
for (auto i : ans) {
cout << i << "\n";
}
}
