Olimpíadas - Maratona 2007

#include <bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
#define endl '\n'
#define W(x) cerr << "\033[31m"<<  #x << " = " << x << "\033[0m" << endl;

using namespace std;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using pii = pair<int, int>;

const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
template <class T = int>
class MCMF{
private:
  struct Edge{
    int to;
    T cap, cost;
    Edge(int a, T b, T c) : to(a), cap(b), cost(c) {}
  };
  int n;
  vector<vector<int>> edges;
  vector<Edge> list;
  vector<int> from;
  vector<T> dist, pot;
  vector<bool> visit;
  pair<T, T> augment(int src, int sink){
    pair<T, T> flow = {list[from[sink]].cap, 0};
    for (int v = sink; v != src; v = list[from[v] ^ 1].to){
      flow.first = std::min(flow.first, list[from[v]].cap);
      flow.second += list[from[v]].cost;
    }
    for (int v = sink; v != src; v = list[from[v] ^ 1].to){
      list[from[v]].cap -= flow.first;
      list[from[v] ^ 1].cap += flow.first;
    }
    return flow;
  }
  queue<int> q;
  bool SPFA(int src, int sink){
    T INF = numeric_limits<T>::max();
    dist.assign(n, INF);
    from.assign(n, -1);
    q.push(src);
    dist[src] = 0;
    while (!q.empty()){
      int on = q.front();
      q.pop();
      visit[on] = false;
      for (auto e : edges[on]){
        auto ed = list[e];
        if (ed.cap == 0)
          continue;
        T toDist = dist[on] + ed.cost + pot[on] - pot[ed.to];
        if (toDist < dist[ed.to]){
          dist[ed.to] = toDist;
          from[ed.to] = e;
          if (!visit[ed.to]){
            visit[ed.to] = true;
            q.push(ed.to);
          }
        }
      }
    }
    return dist[sink] < INF;
  }
  void fixPot(){
    T INF = numeric_limits<T>::max();
    for (int i = 0; i < n; i++){
      if (dist[i] < INF)
        pot[i] += dist[i];
    }
  }
public:
  MCMF(int size){
    n = size;
    edges.resize(n);
    pot.assign(n, 0);
    dist.resize(n);
    visit.assign(n, false);
  }
  pair<T, T> solve(int src, int sink, int mx){
    pair<T, T> ans(0, 0);
    // Can use dijkstra to speed up depending on the graph
    if (!SPFA(src, sink))
      return ans;
    fixPot();
    // Can use dijkstra to speed up depending on the graph
    while (SPFA(src, sink)){
      auto flow = augment(src, sink);
      if(flow.S > mx)
        break;
      ans.first += flow.first*(mx-flow.second+1);
      ans.second += flow.first * flow.second;
      fixPot();
    }
    return ans;
  }
  void addEdge(int u, int to, T cap, T cost){
    edges[u].push_back(list.size());
    list.push_back(Edge(to, cap, cost));
    edges[to].push_back(list.size());
    list.push_back(Edge(u, 0, -cost));
  }
};
struct Edge{
  int a, b, s;
};
int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  while(true){
    int n, m, a;
    cin >> n >> m >> a;
    if(n==0 and m==0 and a==0)
      break;
    vector<Edge> edges(m);
    for(int i=0; i<m; i++){
      cin >> edges[i].a >> edges[i].b >> edges[i].s;
    }
    int lo=1, hi=1000, ans=1000;
    while(lo<=hi){
      int mid = (lo+hi)/2;
      MCMF mcmf(n);
      for(int i=0; i<m; i++)
        mcmf.addEdge(edges[i].a-1, edges[i].b-1, edges[i].s, 1);
      if(mcmf.solve(0, n-1, mid).F >= a){
        ans = mid;
        hi = mid-1;
      }else{
        lo = mid+1;
      }
    }
    cout << ans << endl;
  }
  cout << endl;
  return 0;
}