#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;#define MAXN 1000#define MAXM 100000#define INF 0xFFFFFFstruct edge{int to,c,w,next;};edge e[MAXM];bool in[MAXN];int head[MAXN],dis[MAXN],pre[MAXN],en,maxflow,mincost;int vn,st,ed;int n,m;void add(int a,int b,int c,int d){e[en].to=b;e[en].c=c;e[en].w=d;e[en].next=head[a];head[a]=en++;e[en].to=a;e[en].c=0;e[en].w=-d;e[en].next=head[b];head[b]=en++;}bool spfa(int s){queue<int> q;for(int i=0;i<=vn;i++){dis[i]=INF;in[i]=false;pre[i]=-1;}dis[s]=0;in[s]=true;q.push(s);while(!q.empty()){int tag=q.front();in[tag]=false;q.pop();for(int i=head[tag];i!=-1;i=e[i].next){int j=e[i].to;if(e[i].w+dis[tag]<dis[j] && e[i].c){dis[j]=e[i].w+dis[tag];pre[j]=i;if(!in[j]){q.push(j);in[j]=true;}}}}if(dis[ed]==INF)return false;return true;}void update(){int flow=INF; for (int i=pre[ed];i!=-1;i=pre[e[i^1].to])if(e[i].c<flow) flow=e[i].c; for (int i=pre[ed];i!=-1;i=pre[e[i^1].to]) {e[i].c-=flow,e[i^1].c+=flow;} maxflow+=flow; mincost+=flow*dis[ed];}void mincostmaxflow(){maxflow=0,mincost=0;while(spfa(st))update();}int main(){ for(int cs=1;~scanf("%d%d",&n,&m);cs++) { if(n==0 && m==0) break; memset(head,-1,sizeof(head));en=0; st=2*n,ed=2*n+1,vn=2*n+2; for(int i=0;i<n;i++) add(i,i+n,1,0); add(st,0+n,2,0);add(n-1,ed,2,0); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u+n,v,1,w); } mincostmaxflow(); printf("Instance #%d: ",cs); if(maxflow<2) printf("Not possiblen"); else printf("%dn",mincost); } return 0;}
