dinic

using int64 = long long;

constexpr int MAXE = 25000, MAXV = 105, INF = 0x7f7f7f7f;
struct Element
{
    int to, cap, last;
}e[MAXE];

int head[MAXV], head_point = 0;
int dis[MAXV];
bool vis[MAXV];

inline void __init() //call this before you use dinic
{
    memset(head, -1, sizeof(head));
    head_point = 0;
}

inline void addedge(int from, int to, int cap)
{
    e[head_point] = Element{to,cap,head[from]};
    head[from] = head_point++;

    e[head_point] = Element{from,cap,head[to]};
    head[to] = head_point++;
}

bool __bfs(int s, int t)
{
    memset(vis, false, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));

    queue<int> qu;

    vis[s] = true;
    dis[s] = 0;
    qu.emplace(s);

    while(!qu.empty())
    {
        int now = qu.front(); qu.pop();
        for(int i = head[now]; i != -1; i = e[i].last)
        {
            int to = e[i].to;
            if(e[i].cap > 0 && !vis[to])
            {
                dis[to] = dis[now] + 1;
                vis[to] = true;
                qu.emplace(to);
                if(to == t) return true;
            }
        }
    }
    return false;
}
int __dfs(int now, int flow, int s, int t)
{
    if(now==t) return flow;
    if(vis[now]) return 0;

    vis[now] = true;

    for(int i = head[now]; i != -1; i = e[i].last)
    {
        int to = e[i].to;
        if(e[i].cap > 0 && dis[to] == dis[now] + 1)
        {
            int max_flow = __dfs(to, min(flow, e[i].cap), s, t);
            if(max_flow != 0)
            {
                e[i].cap -= max_flow;
                e[i^1].cap += max_flow;
                return max_flow;
            }
        }
    }
    return 0;
}
int64 __dinic(int s, int t)
{
    int64 result_flow = 0;
    while(__bfs(s, t))
        while(true)
        {
            memset(vis, false, sizeof(vis));
            int f = __dfs(s, INF, s, t);
            if(f == 0) break;
            result_flow += f;
        }
    return result_flow;
}
int main()
{
    int in_n, in_s, in_t, in_c, in_from, in_to, in_cap, kase = 1;
    while(~scanf("%d", &in_n) && in_n)
    {
        __init();

        scanf("%d %d %d", &in_s, &in_t, &in_c);
        for(int i = 0; i < in_c && scanf("%d %d %d", &in_from, &in_to, &in_cap); i++)
            addedge(in_from, in_to, in_cap);

        printf("Network %d\n", kase++);
        printf("The bandwidth is %lld.\n\n", __dinic(in_s, in_t));
    }
    return 0;
}