先跑一遍最大流，然后对最大流上的边注意扩容，每次完成后回复流量；

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const long long inf=3e9;
int cnt=1,n,m,last[115],ceng[115],cur[115],g[115][115],num,flag,f0,ud[20005],id[20005],id1[20005],p;
long long c,flow,mflow;
struct edge
{
    int v,next;
    long long f,rf;
}e[21005];
inline void add(int u,int v,int f)
{
    e[++cnt].v=v;
    e[cnt].next=last[u];
    e[cnt].f=f;
    last[u]=cnt;
    e[++cnt].v=u;
    e[cnt].f=0;
    e[cnt].next=last[v];
    last[v]=cnt;
}
bool bfs()
{
    memset(ceng,0,sizeof(ceng));
    ceng[1]=1;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=last[u];i;i=e[i].next)
        {
            long long v=e[i].v,f=e[i].f,rf=e[i].rf;
            if(!ceng[v]&&f>rf)
            {
                ceng[v]=ceng[u]+1;
                q.push(v);
            }
        }
    }
    return ceng[n];
}
long long dfs(int u,long long dis)
{
    if(!dis||u==n) return dis;
    for(int i=cur[u];i;i=e[i].next)
    {
        cur[u]=e[i].next;
        long long v=e[i].v,f=e[i].f,rf=e[i].rf;
        if(f>rf&&ceng[v]==ceng[u]+1)
        {
            long long di=dfs(v,min(dis,f-rf));
            if(di>0)
            {
                e[i].rf+=di;
                e[i^1].rf-=di;
                return di;
            }
        }
    }
    return 0;
}
void getflow()
{
    for(int i=2;i<=cnt;i++)
    e[i].rf=ud[i];
}
void dinic()
{
    while(bfs())
    {
        for(int i=1; i<=n; i++)
        cur[i]=last[i];
        while(long long d=dfs(1,inf))
        flow+=d;
        if(flow>=c)
        break;
    }
    if(flow>=c)
    {
        printf("Case %d: possible",num);
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=last[i];j;j=e[j].next)
        {
            int v=e[j].v,f=e[j].f,rf=e[j].rf;
            ud[j]=rf;
            if(rf>0&&ceng[i]&&!ceng[v]&&rf==f)
           {
                id[++p]=j;
                id1[p]=i;
           }

            e[j].f-=e[j].rf;
        }
    }
    for(int i=1;i<=p;i++)
    {
                getflow();
                e[id[i]].f=c;
                mflow=flow;
                while(bfs())
                {
                    for(int k=1;k<=n;k++)
                    cur[k]=last[k];
                    while(long long d=dfs(1,inf))
                    {
                        mflow+=d;
                        if(mflow>=c)
                        break;
                    }
                    if(mflow>=c)
                    break;
                }
                if(!flag&&mflow>=c)
                {
                    printf("Case %d: possible option:(%d,%d)",num,id1[i],e[id[i]].v);
                    flag=1;
                } else if(mflow>=c)
                printf(",(%d,%d)",id1[i],e[id[i]].v);
    }
    if(!flag)
    printf("Case %d: not possible",num);
}
void intt()
{
    for(int i=1;i<=cnt;i++)
    e[i].f=e[i].v=e[i].rf=e[i].next=0;
    flag=flow=mflow=p=0;
    memset(last,0,sizeof(last));
    memset(ud,0,sizeof(ud));
    memset(id,0,sizeof(id));
    memset(id1,0,sizeof(id1));
    cnt=1;
}
int main()
{
    while(cin>>n>>m>>c)
    {
        num++;
        if(f0)
        cout<<endl;
        if(!n&&!m&&!c)
        break;
        for(int i=1,u,v;i<=m; i++)
        {
            long long w;
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,w);
        }
        f0=1;
        dinic();
        intt();
    }
    return 0;
}