"Shortest" pair of paths

//============================================================================
// Name        : ACM
// Author      : Tarango Khan
// Team        : BRACU Byteheads
//============================================================================

#include <bits/stdc++.h>
using namespace std;
#define Size 22
#define INF 99999999

int Set(int N,int pos){
    return N = N | (1<<pos);
}

bool Check(int N,int pos){
    return (bool)(N & (1<<pos));
}

struct Edge {
    int v, w;
    Edge(int vv, int c) {
        v = vv;
        w = c;
    }
    bool operator <(const Edge& other) const {
        return w > other.w;
    }
};

priority_queue<Edge> pQ;
int dist[Size];
int vert, edge;
vector<Edge> Graph[Size];
bool taken[22];
vector<int> sp;
int DP[(1<<20)+5][21];

int dijkstra() {
    dist[0] = 0;
    pQ = priority_queue<Edge>();
    dist[0] = 0;
    pQ.push(Edge(0, 0));
    while (!pQ.empty()) {
        Edge cur = pQ.top();
        pQ.pop();
        int Sz = Graph[cur.v].size();
        for (int i = 0; i < Sz; i++) {
            Edge e = Graph[cur.v][i];
            if(taken[e.v] == true) continue;
            if (cur.w + e.w < dist[e.v]) {
                dist[e.v] = cur.w + e.w;
                pQ.push(Edge(e.v, dist[e.v]));
            }
        }
    }
    return dist[vert-1];
}

int secondPath(int mask){
    bool others = false;
    for(int i = 0;i<=vert;i++){
        dist[i]= INF;
        taken[i] = false;
    }
    //Marking those nodes so that next shortest path doesn't include them;
    for(int p = 1;p<vert-1;p++){
        if(Check(mask,p) == true){
            taken[p] = true;
            others = true;
        }
    }
    //For handling test cases where shortest path include only (src-dest) edge;
    if(sp.size() != 0){
        if(others == false){ //Means the previous path includes only  (src-dest) edge;
            int Sz = Graph[0].size();
            for(int i = 0;i<Sz;i++){
                if(Graph[0][i].v == vert-1 && Graph[0][i].w == sp[0]){
                    Graph[0][i].w = INF;
                    int ret = dijkstra();
                    Graph[0][i].w = sp[0];
                    return ret;
                }
            }
        }
    }
    return dijkstra();
}

int call(int cur,int mask){
    if(cur == vert-1){
        //After successfully finding a path from src to dest,
        //Searching the next shortest path using dijkstra;
        return secondPath(mask);
    }
    if(DP[mask][cur] != -1) return DP[mask][cur];

    int Sz = Graph[cur].size();
    int res = INF;
    for(int i = 0;i<Sz;i++){
        Edge e = Graph[cur][i];
        if(Check(mask,e.v) == false){
            int nMask = Set(mask,e.v);
            int ret = call(e.v,nMask) + e.w;
            res = min(res,ret);
        }
    }
    return DP[mask][cur] = res;
}

int main() {
    int source,dest,w,cs = 0;;
    while (scanf("%d %d",&vert,&edge) == 2) {
        cs++;
        if(vert == 0 && edge == 0) break;
        sp.clear(); //sp includes only the edge cost of (src-dest);
        for (int i = 0; i <= vert; i++) {
            dist[i] = INF;
            taken[i] = false;
            Graph[i].clear();
        }
        for (int i = 0; i < edge; i++) {
            scanf("%d %d %d", &source, &dest, &w);
            Graph[source].push_back(Edge(dest, w));
            if(source == 0 && dest == vert-1){
                sp.push_back(w);
            }
        }
        sort(sp.begin(),sp.end());
        memset(DP,-1,sizeof(DP));
        int res = call(0,1);
        if(res < INF){
            printf("Instance #%d:  %d\n",cs,res);
        }else{
            printf("Instance #%d:  Not possible\n",cs);
        }
    }
    return 0;
}