```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 5, M = 1e5 + 5, inf = 1e18;
int n, m, k, fir[N], nxt[M << 1], son[M << 1], eage[M << 1], w[M << 1], ans, val[N][N], x, y, z, tot = 1, V, d[N], q[N], h, t, pre[N], flow[N], TTT, s, ans1, ans2;
bool vis[N];
inline void add(int x, int y, int z, int flow){
nxt[++tot] = fir[x];
fir[x] = tot;
son[tot] = y;
eage[tot] = flow;
w[tot] = z;
}
inline void Add(int x, int y, int z, int flow){
add(x, y, z, flow);
add(y, x, -z, 0);
}
inline void calc(int &x){
x++;
if(x >= n + 1) x -= n + 1;
}
inline bool spfa(){
for(int i = 1; i <= n; i++) d[i] = inf, vis[i] = 0;
h = 0, q[t = 1] = s, d[s] = 0, vis[s] = 1, flow[s] = inf;
while(h != t){
//for(int i = 1; i <= n; i++) cout << d[i] << ' ';
//cout << endl;
//cout << h << ' ' << t << endl;
calc(h);
//cout << "SPFA " << q[h] << ' ' << h << ' ' << t << '\n';
x = q[h];
vis[x] = 0;
for(int i = fir[x]; i ; i = nxt[i]){
if(eage[i] && d[son[i]] > d[x] + w[i]){
d[son[i]] = d[x] + w[i];
pre[son[i]] = i;
flow[son[i]] = min(flow[x], eage[i]);
if(vis[x] == 0){
calc(t);
q[t] = son[i];
vis[son[i]] = 0;
}
}
}
}
//cerr << "SPFA_NEAR_DONE\n" << d[n] << endl;
return d[n] < inf;
}
inline void upd(){
x = n;
ans2 += d[n] * flow[n];
ans1 += flow[n];
for(; x != s;){
x = pre[x];
eage[x] -= flow[n];
eage[x ^ 1] += flow[n];
x = son[x ^ 1];
}
}
signed main(){
//freopen("data.in", "r", stdin);
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) val[i][j] = inf;
for(int i = 1; i <= m; i++){
scanf("%lld%lld%lld", &x, &y, &z);
Add(x, y, 0, z);
scanf("%lld", &z);
val[x][y] = min(val[x][y], z);
}
s = 1;
while(spfa()){
d[n] = 1;
//cerr << "SPFA_DONE\n";
upd();
}
//cerr << "BREAK\n";
printf("%lld ", ans1);
ans2 = 0;
TTT = tot;
for(x = 1; x <= n; x++){
for(int i = fir[x]; i ; i = nxt[i]){
if(i & 1 || i > TTT) continue ;
y = son[i];
V = val[x][y];
Add(x, y, V, inf);
}
}
ans = 0;
Add(0, 1, 0, k);
s = 0;
while(spfa()){
//cerr << "SPFA_DONE\n";
upd();
}
printf("%lld\n", ans2);
return 0;
}
```
by huangrenheluogu @ 2023-11-28 16:36:58