mincost.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> II;

const int N = 105;

int n, m, k, s, t;
vector<int> adj[N];
int cost[N][N], capa[N][N], flow[N][N];
int dist[N], water[N], prv[N];

template<typename T>
bool chmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}

bool bmf(int k) {
  memset(dist, 0x3f, sizeof(dist));
  memset(water, 0, sizeof(water));
  queue<II> q; q.push({0, s});
  dist[s] = 0; water[s] = k;
  while (q.size()) {
    int d, i;
    tie(d, i) = q.front(); q.pop();
    if (d > dist[i]) continue;
    for (auto &j : adj[i]) {
      bool b = (flow[i][j] >= 0);
      int f = (b ? capa[i][j] - flow[i][j] : -flow[i][j]);
      if (f == 0) continue;
      if (chmin(dist[j], dist[i] + cost[i][j] * (b ? 1 : -1))) {
        water[j] = min(water[i], f);
        prv[j] = i;
        q.push({dist[j], j});
      }
    }
  }
  return water[t];
}

void incFlow() {
  for (int i = t; i != s; i = prv[i]) {
    flow[prv[i]][i] += water[t];
    flow[i][prv[i]] -= water[t];
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k >> s >> t;
  for (int i = 1; i <= m; i++) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    adj[u].push_back(v);
    adj[v].push_back(u);
    cost[u][v] = cost[v][u] = c;
    capa[u][v] = capa[v][u] = d;
  }
  int ans = 0;
  while (k > 0 && bmf(k)) {
    incFlow();
    k -= water[t];
    ans += dist[t] * water[t];
  }
  if (k > 0) {
    cout << -1 << '\n';
    return 0;
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    for (auto &j : adj[i]) {
      if (flow[i][j] > 0) {
        cout << i << ' ' << j << ' ' << flow[i][j] << '\n';
      }
    }
  }
  cout << "0 0 0" << '\n';
}