Min Cost Max Flow

#define ll                     long long
#define INF                    123456789

static const int MAXN = 5*100+5;

vector <int> graph[MAXN];
ll cap[MAXN][MAXN], flow[MAXN][MAXN], cost[MAXN][MAXN], dis[MAXN];
int father[MAXN];
bool vis[MAXN], inQueue[MAXN];

bool SPFA(int S, int T)
{
    fill(begin(dis), end(dis), INF);
    fill(begin(inQueue), end(inQueue), false);
    queue <int> PQ;
    PQ.push(S);
    dis[S] = 0;
    inQueue[S] = true;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        inQueue[u] = false;
        for (int v : graph[u])
        {
            if (flow[v][u] > 0 && dis[u] + (-cost[v][u]) < dis[v])
            {
                dis[v] = dis[u] + (-cost[v][u]);
                father[v] = u;
                if (!inQueue[v])
                {
                    inQueue[v] = true;
                    PQ.push(v);
                }
            }
            else if (cap[u][v] > flow[u][v] && dis[u] + cost[u][v] < dis[v])
            {
                dis[v] = dis[u] + cost[u][v];
                father[v] = u;
                if (!inQueue[v])
                {
                    inQueue[v] = true;
                    PQ.push(v);
                }
            }
        }
    }
    return dis[T] != INF;
}

ll findMinFlow(int S, int T)
{
    ll bottleneck = INF;
    for (int u = T; u != S; u = father[u])
        bottleneck = min(bottleneck, cap[father[u]][u] - flow[father[u]][u]);
    return bottleneck;
}

void updateFlow(int S, int T, ll bottleneck)
{
    for (int u = T; u != S; u = father[u])
    {
        flow[father[u]][u] += bottleneck;
        flow[u][father[u]] -= bottleneck;
    }
}

ll MCMF(int S, int T)
{
    ll maxFlow = 0;
    ll minCost = 0;
    while (SPFA(S, T))
    {
        ll bottleneck = findMinFlow(S, T);
        updateFlow(S, T, bottleneck);
        maxFlow += bottleneck;
        minCost += (dis[T] * bottleneck);
    }
    if (maxFlow == 2)
        return minCost;
    return -1;
}

void INITIALIZE()
{
    for (int i = 0; i < MAXN; i++)
    {
        graph[i].clear();
    }
    memset(flow, 0, sizeof(flow));
    memset(cap, 0, sizeof(cap));
    memset(cost, 0, sizeof(cost));
}

int main()
{
    //freopen("in.txt", "r", stdin);

    int tNode, tEdge;
    while (scanf("%d", &tNode) == 1)
    {
        if (tNode == 0)
            break;
        INITIALIZE();
        scanf("%d", &tEdge);
        for (int e = 0; e < tEdge; e++)
        {
            int u, v;
            ll c;
            scanf("%d %d %lld", &u, &v, &c);

            graph[u].push_back(v);
            graph[v].push_back(u);

            cap[u][v] = cap[v][u] = 1;
            cost[u][v] = cost[v][u] = c;
        }
        int S = 0;
        int T = tNode + 1;

        graph[S].push_back(1);
        graph[1].push_back(S);

        cost[S][1] = cost[1][S] = 0;
        cap[S][1] = cap[1][S] = 2;

        graph[tNode].push_back(T);
        graph[T].push_back(tNode);

        cost[tNode][T] = cost[T][tNode] = 0;
        cap[tNode][T] = cap[T][tNode] = 2;

        ll res = MCMF(S, T);
        if (res == -1)
            puts("Back to jail");
        else
            printf("%lld\n", res);
    }
}
#define ll                     long long
#define INF                    123456789

static const int MAXN = 5*100+5;

vector <int> graph[MAXN];
ll cap[MAXN][MAXN], flow[MAXN][MAXN], cost[MAXN][MAXN], dis[MAXN];
int father[MAXN];
bool vis[MAXN], inQueue[MAXN];

bool SPFA(int S, int T)
{
    fill(begin(dis), end(dis), INF);
    fill(begin(inQueue), end(inQueue), false);
    queue <int> PQ;
    PQ.push(S);
    dis[S] = 0;
    inQueue[S] = true;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        inQueue[u] = false;
        for (int v : graph[u])
        {
            if (flow[v][u] > 0 && dis[u] + (-cost[v][u]) < dis[v])
            {
                dis[v] = dis[u] + (-cost[v][u]);
                father[v] = u;
                if (!inQueue[v])
                {
                    inQueue[v] = true;
                    PQ.push(v);
                }
            }
            else if (cap[u][v] > flow[u][v] && dis[u] + cost[u][v] < dis[v])
            {
                dis[v] = dis[u] + cost[u][v];
                father[v] = u;
                if (!inQueue[v])
                {
                    inQueue[v] = true;
                    PQ.push(v);
                }
            }
        }
    }
    return dis[T] != INF;
}

ll findMinFlow(int S, int T)
{
    ll bottleneck = INF;
    for (int u = T; u != S; u = father[u])
        bottleneck = min(bottleneck, cap[father[u]][u] - flow[father[u]][u]);
    return bottleneck;
}

void updateFlow(int S, int T, ll bottleneck)
{
    for (int u = T; u != S; u = father[u])
    {
        flow[father[u]][u] += bottleneck;
        flow[u][father[u]] -= bottleneck;
    }
}

ll MCMF(int S, int T)
{
    ll maxFlow = 0;
    ll minCost = 0;
    while (SPFA(S, T))
    {
        ll bottleneck = findMinFlow(S, T);
        updateFlow(S, T, bottleneck);
        maxFlow += bottleneck;
        minCost += (dis[T] * bottleneck);
    }
    if (maxFlow == 2)
        return minCost;
    return -1;
}

void INITIALIZE()
{
    for (int i = 0; i < MAXN; i++)
    {
        graph[i].clear();
    }
    memset(flow, 0, sizeof(flow));
    memset(cap, 0, sizeof(cap));
    memset(cost, 0, sizeof(cost));
}

int main()
{
    //freopen("in.txt", "r", stdin);

    int tNode, tEdge;
    while (scanf("%d", &tNode) == 1)
    {
        if (tNode == 0)
            break;
        INITIALIZE();
        scanf("%d", &tEdge);
        for (int e = 0; e < tEdge; e++)
        {
            int u, v;
            ll c;
            scanf("%d %d %lld", &u, &v, &c);

            graph[u].push_back(v);
            graph[v].push_back(u);

            cap[u][v] = cap[v][u] = 1;
            cost[u][v] = cost[v][u] = c;
        }
        int S = 0;
        int T = tNode + 1;

        graph[S].push_back(1);
        graph[1].push_back(S);

        cost[S][1] = cost[1][S] = 0;
        cap[S][1] = cap[1][S] = 2;

        graph[tNode].push_back(T);
        graph[T].push_back(tNode);

        cost[tNode][T] = cost[T][tNode] = 0;
        cap[tNode][T] = cap[T][tNode] = 2;

        ll res = MCMF(S, T);
        if (res == -1)
            puts("Back to jail");
        else
            printf("%lld\n", res);
    }
}