#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, u, v;
    ll x, c, t;
    cin >> n >> m >> x;
    atcoder::mcf_graph<int, ll> g(n);
	while(m--){
        cin >> u >> v >> c >> t;
        g.add_edge(--u, --v, 1, c += t * x);
        g.add_edge(v, u, 1, c);
    }
    auto [fl, ans] = g.flow(0, n - 1, 1);
    cout << (fl ? (ans + x - 1) / x : -1) << '\n';
}