include <bits/stdc++.h>

using namespace std;

const int maxn =  + ;

const int INF = 0x3f3f3f3f;

struct Edge {

    int from,to,cap,flow;

};

bool operator < (const Edge& a,const Edge& b) {

    return a.from < b.from || (a.from==b.from&&a.to<b.to);

}

struct Dinic {

    int n,m,s,t;

    vector<Edge> edges;

    vector<int> G[maxn];

    bool vis[maxn];

    int d[maxn];

    int cur[maxn];

    void init(int n) {

        for(int i=;i<n;i++)

            G[i].clear();

        edges.clear();

    }

    void ClearFlow() {

        for(int i=;i<edges.size();i++) {

            edges[i].flow = ;

        }

    }

    void AddEdge(int from,int to,int cap) {

        edges.push_back((Edge){from,to,cap,});

        edges.push_back((Edge){to,from,,});

        m = edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    bool BFS() {

        memset(vis,,sizeof(vis));

        queue<int> Q;

        Q.push(s);

        vis[s] = ;

        d[s] = ;

        while(!Q.empty()) {

            int x = Q.front();

            Q.pop();

            for(int i=;i<G[x].size();i++) {

                Edge& e = edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow) {

                    vis[e.to] = ;

                    d[e.to] = d[x] + ;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x,int a) {

        if(x==t||a==) return a;

        int flow =,f;

        for(int& i=cur[x];i<G[x].size();i++) {

            Edge& e = edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>) {

                e.flow +=f;

                edges[G[x][i]^].flow -=f;

                flow +=f;

                a-=f;

                if(a==) break;

            }

        }

        return flow;

    }

    int Maxflow(int s,int t) {

        this->s = s;

        this->t = t;

        int flow = ;

        while(BFS()) {

            memset(cur,,sizeof(cur));

            flow +=DFS(s,INF);

        }

        return flow;

    }

    vector<int> Mincut() {

        vector<int> ans;

        for(int i=;i<edges.size();i++) {

            Edge& e = edges[i];

            if(vis[e.from]&&!vis[e.to]&&e.cap>)

                ans.push_back(i);

        }

        return ans;

    }

    void Reduce () {

        for(int i=;i<edges.size();i++)

            edges[i].cap -=edges[i].flow;

    }

};

Dinic g;

int main()

{

    int kase = ;

    int n,e,c;

    while(scanf("%d%d%d",&n,&e,&c)==&&n) {

        g.init(n);

        for(int i=;i<e;i++) {

            int u,v,cap;

            scanf("%d%d%d",&u,&v,&cap);

            u--;v--;

            g.AddEdge(u,v,cap);

        }

        printf("Case %d: ",kase ++);

        int flow = g.Maxflow(,n-);

        if(flow>=c) printf("possible\n");

        else {

            vector<int> cut = g.Mincut();

            g.Reduce();

            vector<Edge> ans;

            for(int i=;i<cut.size();i++) {

                Edge& e = g.edges[cut[i]];

                int temp = e.cap;   ///

                e.cap = c;

                g.ClearFlow();

                if(flow+g.Maxflow(,n-)>=c)

                    ans.push_back(e);

                e.cap = temp;       ///

            }

            if(ans.empty())

                printf("not possible\n");

            else {

                sort(ans.begin(),ans.end());

                printf("possible option:(%d,%d)",ans[].from+,ans[].to + );

                for(int i=;i<ans.size();i++) {

                    printf(",(%d,%d)",ans[i].from+,ans[i].to+);

                }

                puts("");

            }

        }

    }

    return ;

}