1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 using namespace std;
 11 #define pb push_back
 12 #define lc(x) (x << 1)
 13 #define rc(x) (x << 1 | 1)
 14 #define lowbit(x) (x & (-x))
 15 #define ll long long
 16 #define maxn 2000
 17 #define maxm 50000
 18 const int inf = 1 << 30;
 19 int s, t, n, m;
 20 struct Edge {
 21     int u, v, w, cost, next;
 22 }et[maxm];
 23 
 24 struct edge {
 25     int u, v, cap, flow, next;
 26 }et2[maxm];
 27 
 28 int eh[maxn], tot, dist[maxn];
 29 bool visit[maxn];
 30 int eh2[maxn], tot2, low[maxn], dist2[maxn], pre[maxn], cur[maxn], cnt[maxn];
 31 
 32 void init() {
 33     tot = 0;
 34     tot2 = 0;
 35     memset(eh, -1, sizeof (eh));
 36     memset(eh2, -1, sizeof (eh2));
 37 }
 38 
 39 void addedge(int u, int v, int w, int cost) {
 40     Edge e = {u, v, w, cost, eh[u]};
 41     et[tot] = e;
 42     eh[u] = tot++;
 43 }
 44 
 45 void add(int u, int v, int cap, int flow) {
 46     edge e = {u, v, cap, flow, eh2[u]};
 47     et2[tot2] = e;
 48     eh2[u] = tot2++;
 49 }
 50 
 51 void addedge2(int u, int v, int cap) {
 52     add(u, v, cap, 0), add(v, u, 0, 0);
 53 }
 54 
 55 void spfa(int s) {
 56     for (int i = 0; i <= n; i++) visit[i] = false, dist[i] = inf, cnt[i] = 0;//dist[i] = -inf;
 57     dist[s] = 0, visit[s] = true;
 58     queue<int> que;
 59     que.push(s);
 60     while (!que.empty()) {
 61         int u = que.front();
 62         que.pop(), visit[u] = false;
 63         for (int i = eh[u]; i != -1; i = et[i].next) {
 64           int v = et[i].v, w = et[i].w;
 65             if (dist[v] > w + dist[u]) {//dist[v] < w + dist[u]
 66                 dist[v] = w + dist[u];
 67                 if (!visit[v]) {
 68                     visit[v] = true;
 69                     que.push(v);
 70                 }
 71             }
 72         }
 73     }
 74 }
 75 
 76 void build() {
 77     for(int i = 0; i < tot; i++) {
 78         int u = et[i].u, v = et[i].v, w = et[i].w, cost = et[i].cost;
 79         if(dist[u] + w == dist[v]) {
 80             addedge2(u, v, cost);
 81         }
 82     }
 83 }
 84 
 85 int isap(int s, int t, int n){
 86     int u, v, now, flow = 0;
 87     memset(dist2, 0, sizeof(dist2)); 
 88     memset(low, 0, sizeof(low));
 89     memset(cnt, 0, sizeof(cnt));
 90     for(u = 0 ; u <= n ; u++) cur[u] = eh2[u];
 91     low[s] = inf, cnt[0] = n, u = s;
 92     while(dist2[s] < n) {
 93         for(now = cur[u]; now != -1; now = et2[now].next)
 94             if(et2[now].cap - et2[now].flow && dist2[u] == dist2[ v = et2[now].v ] + 1 ) break;
 95         if(now != -1) {
 96             cur[u] = pre[v] = now;
 97             low[v] = min(et2[now].cap - et2[now].flow, low[u]);
 98             u = v;
 99             if(u == t) {
100                 for(; u != s; u = et2[pre[u]].u){
101                     et2[pre[u]].flow += low[t];
102                     et2[pre[u]^1].flow -= low[t];
103                 }
104                 flow += low[t]; low[s] = inf;
105             }
106         } else {
107             if(--cnt[dist2[u]] == 0) break;
108             dist2[u] = n, cur[u] = eh2[u];
109             for(now = eh2[u]; now != -1; now = et2[now].next)
110                 if(et2[now].cap - et2[now].flow && dist2[u] > dist2[et2[now].v] + 1)
111                     dist2[u] = dist2[et2[now].v] + 1;
112             cnt[dist2[u]]++;
113             if(u != s) u = et2[pre[u]].u;
114         }
115     }
116     return flow;
117 }
118 
119 int main() {
120     int u, v, w, c;
121     int Case = 1;
122     while(~scanf("%d%d", &n, &m)) {
123         if(!n && !m) break;
124         scanf("%d%d", &s, &t);
125         init();
126         for(int i = 0; i < m; i++) {
127             scanf("%d%d%d%d", &u, &v, &w, &c);
128             addedge(u, v, w, c);
129             addedge(v, u, w, c);
130         }
131         spfa(s);
132         build();
133         int ans = isap(s, t, n);
134         printf("Case %d: %d\n", Case++, ans);
135     }
136     return 0;
137 }
138