1 #include <cstring>  2 #include <cstdio>  3 #include <vector>  4 #include <queue>  5 #include <algorithm>  6 #include <iostream>  7 using namespace std;  8   9 const int maxn = 100 + 10, INF = 1000000000; 10  11  12 struct Edge 13 { 14     int from, to, cap, flow, cost; 15 }; 16  17 struct MCMF 18 { 19     int n, m; 20     vector<Edge> edges; 21     vector<int> G[maxn]; 22     bool inq[maxn];         // 是否在队列中 23     int d[maxn];           // Bellman-Ford 24     int p[maxn];           // 上一条弧 25     int a[maxn];           // 可改进量 26  27     void init(int n) 28     { 29         this->n = n; 30         for(int i = 0; i < n; i++) G[i].clear(); 31         edges.clear(); 32     } 33  34     void AddEdge(int from, int to, int cap, int cost) 35     { 36         edges.push_back((Edge) 37         { 38             from, to, cap, 0, cost 39         }); 40         edges.push_back((Edge) 41         { 42             to, from, 0, 0, -cost 43         }); 44         m = edges.size(); 45         G[from].push_back(m-2); 46         G[to].push_back(m-1); 47     } 48  49     bool BellmanFord(int s, int t, int &flow, long long& cost) 50     { 51         memset(inq,0,sizeof(inq)); 52         for(int i=0;i<n;i++) 53             d[i] = INF; 54         d[s] = 0; 55         inq[s] = true; 56         p[s] = 0; 57         a[s] = INF; 58  59         queue<int> Q; 60         Q.push(s); 61         while(!Q.empty()) 62         { 63             int u = Q.front(); 64             Q.pop(); 65             inq[u] = false; 66             for(int i = 0; i < G[u].size(); i++) 67             { 68                 Edge& e = edges[G[u][i]]; 69                 if(e.cap > e.flow && d[e.to] > d[u] + e.cost) 70                 { 71                     d[e.to] = d[u] + e.cost; 72                     p[e.to] = G[u][i]; 73                     a[e.to] = min(a[u], e.cap - e.flow); 74                     if(!inq[e.to]) 75                     { 76                         Q.push(e.to); 77                         inq[e.to] = true; 78                     } 79                 } 80             } 81         } 82         if(d[t] == INF) return false; //s-t 不连通，失败退出 83         flow += a[t]; 84         cost += (long long)d[t] * (long long)a[t]; 85         int u = t; 86         while(u != s) 87         { 88             edges[p[u]].flow += a[t]; 89             edges[p[u]^1].flow -= a[t]; 90             u = edges[p[u]].from; 91         } 92         return true; 93     } 94  95      pair<long long,int>Mincost(int s, int t) 96     { 97         long long cost = 0; 98         int flow = 0; 99         while(BellmanFord(s, t, flow, cost));100         return pair<long long ,int>{cost,flow};101     }102 };103 104 MCMF solver;105 int n;106 107 108 int main()109 {110     while(true)111     {112         scanf("%d", &n);113         if(n == 0) break;114         solver.init(n + 1);115         int m, from, to, cost;116         scanf("%d", &m);117         for(int i = 0; i < m; i++)118         {119             scanf("%d%d%d", &from, &to, &cost);120             solver.AddEdge(from, to, 1, cost);121             solver.AddEdge(to, from, 1, cost);122         }123         solver.AddEdge(0, 1, 2, 0);124 125         pair<long long,int> ans = solver.Mincost(0, n);126         int flow = ans.second;127 128         if(flow != 2)129             puts("Back to jail");130         else131             printf("%lld\n", ans.first);132     }133     return 0;134 }