我的思路就是先跑一遍Dinic，如果最大流大于 $C$ 就输出 possible。然后把当前最小割中的边取出来，枚举每条边把流量扩大 $C$，如果最大流大于 $C$ 的话就可以加入答案。

但是这题WA了三天都没改对。。Dinic 和我一直用的板子写的一样，我也试过枚举最小割的可行边（代码里注释掉的get_access函数）但是都没有用，样例都能过，uDebug上的数据也都能过。。真不知道怎么办了

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

char getch()
{
	static char buf[1 << 14], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 14, stdin), p1 == p2) ? EOF : *p1++;
}

void read(ll &x)
{
	x = 0;
	char c = getch();
	while(c < '0' || c > '9') c = getch();
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getch();
	}
}

vector<ll> vec;
vector<pair<ll, ll> > ans;
namespace Dinic
{
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    const ll Maxn = 1000000 + 10;
    const ll Maxm = 5000000 + 10;
    ll cnt = 1, n, s, t;
    ll head[Maxn], dep[Maxn], cur[Maxn];
    struct node
    {
        ll u, v, flow, next;
    }e[Maxm << 1];
	void reset()//使所有边的流量复原
	{
		for(ll i = 2; i <= cnt; i += 2)
		{
			e[i].flow += e[i ^ 1].flow;
			e[i ^ 1].flow = 0;
		}
	}
	void clear()//清空整张图
	{
		for(ll i = 1; i <= n; ++i) head[i] = 0;
		cnt = 1; n = 0;
		//n表示遇到的最大的节点编号，方便清空
	}
    void add(ll u, ll v, ll flow)
    {
		n = max(n, u); n = max(n, v);
		e[++cnt].u = u;
        e[cnt].v = v;
        e[cnt].flow = flow;
        e[cnt].next = head[u];
        head[u] = cnt;

		e[++cnt].u = v;
        e[cnt].v = u;
        e[cnt].flow = 0;
        e[cnt].next = head[v];
        head[v] = cnt;
    }
    ll bfs()
    {
        for(ll i = 1; i <= n; ++i) dep[i] = inf;
	    queue<ll> que;
        que.push(s);
        dep[s] = 0;
        cur[s] = head[s];
        while(!que.empty())
        {
            ll u = que.front(); que.pop();
            for(ll i = head[u]; i; i = e[i].next)
            {
                ll v = e[i].v;
				if(e[i].flow && dep[v] == inf)
				{
					que.push(v);
					dep[v] = dep[u] + 1;
					cur[v] = head[v];
					if(v == t) return 1;
				}
            }
        }
		return 0;
    }
    ll dfs(ll u, ll flow)
    {
        if(u == t) return flow;
        ll incf = 0, res = 0;
        for(ll i = cur[u]; i && flow; i = e[i].next)
        {
			cur[u] = i;
            ll v = e[i].v;
			if(e[i].flow && dep[v] == dep[u] + 1)
			{
				incf = dfs(v, min(flow, e[i].flow));
				if(!incf) dep[v] = inf;
				e[i].flow -= incf;
				e[i ^ 1].flow += incf;
				res += incf;
				flow -= incf;
			}
        }
		return res;
    }
    ll main(ll ss, ll tt, ll INF = inf)
    {
		s = ss; t = tt;
		ll maxflow = 0;
        while(maxflow < INF && bfs()) maxflow += dfs(s, inf);
        return maxflow;
    }
	void get_cut()//获取最小割中的边
	{
		bfs();
		for(ll i = 2; i <= cnt; i += 2)
			if(!e[i].flow && dep[e[i].u] != inf && dep[e[i].v] == inf)
				vec.push_back(i);
		//因为 Dinic 最后一遍 bfs 的标号还在
		//这时如果层数 != inf 就是和源点相连的，否则和汇点相连
	}
    /*
    ll dfn[Maxn], low[Maxn], sd[Maxn], ins[Maxn];
	ll dfn_cnt;
	stack<ll> stk;
	void tarjan(ll u)
	{
	    dfn[u] = low[u] = ++dfn_cnt;
	    stk.push(u); ins[u] = 1;
	    for(ll i = head[u]; i; i = e[i].next)
	    {
	        ll v = e[i].v;
			if(!e[i].flow) continue;
	        if(!dfn[v])
	        {
	            tarjan(v);
	            low[u] = min(low[v], low[u]);
	        }
	        else if(ins[v]) low[u] = min(dfn[v], low[u]);
	    }
	    if(dfn[u] == low[u])
	        while(1)
	        {
	            ll x = stk.top(); stk.pop();
	            sd[x] = u;
	            ins[x] = 0;
	            if(u == x) break;
	        }
	}
	void get_access()
	{
        for(ll i = 1; i <= n; ++i)
            dfn[i] = low[i] = sd[i] = ins[i] = 0;
        dfn_cnt = 0;
        while(!stk.empty()) stk.pop();
		for(ll i = 1; i <= n; ++i)
        	if(!dfn[i]) tarjan(i);
		for(ll i = 2; i <= cnt; i += 2)
		{
			if(e[i].flow || sd[e[i].u] == sd[e[i].v]) continue;
			vec.push_back(i);
		}
	}
    */
};

signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("sample.in", "r", stdin);
	freopen("output.out", "w", stdout);
	#endif
    for(ll tt = 1; ; ++tt)
    {
		ll n, m, k;
        read(n); read(m); read(k);
		if(!n && !m && !k) break;
		printf("Case %lld: ", tt);
		Dinic::clear();
        ll s = 1, t = n;
		for(ll i = 1; i <= m; ++i)
		{
			ll u, v, w;
			read(u); read(v); read(w);
			Dinic::add(u, v, w);
		}
		ll pre = Dinic::main(s, t);

		if(k == 0 || pre >= k) printf("possible\n");
		else
		{
			vec.clear(); ans.clear(); Dinic::get_cut();
			for(ll i = 3; i <= Dinic::cnt; i += 2)
				Dinic::e[i].flow = 0;
			//我的反向边流量等于这条边流过的流量
			//所以清空所有反向边相当于是建了一张残量网络的图
			for(ll i = 0; i < vec.size(); ++i)
			{
				Dinic::reset();//重置整张图
				Dinic::e[vec[i]].flow += k;
				if(pre + Dinic::main(s, t, k) >= k)
					ans.push_back(make_pair(Dinic::e[vec[i]].u, Dinic::e[vec[i]].v));
				Dinic::e[vec[i]].flow -= k;
				//正反边的流量和是不变的，之后重置图后就不会有负数
			}
			if(!ans.size()) printf("not possible\n");
			else
			{
				printf("possible option:");
				sort(ans.begin(), ans.end()); //题意排序
				for(ll i = 0; i < ans.size(); ++i)
					printf("(%lld,%lld)%c", ans[i].first, ans[i].second, ",\n"[i + 1 == ans.size()]);
			}
		}
    }
	return 0;
}