#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef long double ld;
const int N = 1e5 + 5, W = 1e5;
int n, m, k, ans;
struct edge {
	int v, l, a;
};
vector <edge> to[N], in[N];
vector <int> from[N];
vector <int> prime;
bool is[N];
map <int, int> mp;
int deg[N];
queue <int> q;
int dep[N];
vector <int> f[N];
void get_prime(void) {
	for (int i = 2; i <= W; ++i) {
		if (!is[i]) prime.push_back(i);
		for (int j = 0; j < prime.size() && i * prime[j] <= W; ++j) {
			is[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
	//for (int i : prime) cout << i << ' ';
	return ;
}
int qpow(int base, int power) {
	int res = 1;
	while (power) {
		if (power & 1) {
			res = res * base;
		}
		power >>= 1;
		base = base * base;
	}
	return res;
}
void Tp_sort(void) {
	for (int i = 1; i <= n; ++i) if (!deg[i]) q.push(i);
	while (!q.empty()) {
		int u = q.front();
		//cout << u << '\n';
		q.pop();
		for (int i = 0; i < to[u].size(); ++i) {
			int v = to[u][i].v, a = to[u][i].a, l = to[u][i].l;
			//cout << v << '\n';
			--deg[v];
			dep[v] = dep[u] + 1;
			if (!dep[u]) {
				int pos = find(from[v].begin(), from[v].end(), u) - from[v].begin();
				//cout << pos << ' ';
				f[v][pos] = l;
			}
			else {
				int pos = find(from[v].begin(), from[v].end(), u) - from[v].begin();
				for (int i = 0; i < in[u].size(); ++i) {
					int a1 = in[u][i].a;
					if (mp[a] == a1) {
						f[v][pos] = max(f[v][pos], f[u][i] + l);
					}
				}
			}
			if (!deg[v]) q.push(v);
		}
	}
	return ;
}
int main(void) {
	cin.tie(0), cout.tie(0);
	get_prime();
	cin >> n >> m >> k;
	for (int i = 1, u, v, w, a, l, b; i <= m; ++i) {
		a = b = 1;
		cin >> u >> v >> w >> l;
		int tn = w;
		for (int i : prime) {
			if (tn == 1) break;
			if (tn % i != 0) continue;
			int num = 0;
			while (tn % i == 0) {
				++num;
				tn /= i;
			}
			num %= k;
			a *= qpow(i, num);
			b *= qpow(i, k - num);
		}
		in[v].push_back((edge){u, l, a});
		to[u].push_back((edge){v, l, a});
		mp[a] = b;
		++deg[v];
		from[v].push_back(u);
		f[v].push_back(0);
	}
	/*for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < f[i].size(); ++j) {
			cout << f[i][j];
		}
		cout << '\n';
	}*/
	Tp_sort();
	for (int i = 1; i <= n; ++i)
		for (int j : f[i]) ans = max(ans, j);
	cout << ans;
	return 0;
}