/*参考博文:http://hi.baidu.com/dragon_eric123/item/82e259200ece744046996282 有上下界的有源最小流 */ #include<stdio.h> #include<string.h> #include<queue> using namespace std; #define N 300 #define inf 0x3fffffff struct node { int u,v,w,f,next; }bian[N*N*2]; int head[N],yong,dis[N],work[N]; void init(){ yong=0; memset(head,-1,sizeof(head)); } void addbian(int u,int v,int w,int f) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].f=f; bian[yong].next=head[u]; head[u]=yong++; } void add(int u,int v,int w,int f) { addbian(u,v,w,f); addbian(v,u,0,f); } int min(int a,int b) { return a<b?a:b; } int bfs(int s,int t) { memset(dis,-1,sizeof(dis)); queue<int>q; q.push(s); dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==-1) { dis[v]=dis[u]+1; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int s,int limit,int t) { if(s==t)return limit; for(int &i=work[s];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==dis[s]+1) { int tt=dfs(v,min(limit,bian[i].w),t); if(tt) { bian[i].w-=tt; bian[i^1].w+=tt; return tt; } } } return 0; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) { memcpy(work,head,sizeof(head)); while(int tt=dfs(s,inf,t)) ans+=tt; } return ans; } int main() { int n,m,i,a,b,c,d,w[N],sum,f,ff,index,s,t; while(scanf("%d%d",&n,&m)!=EOF) { init(); s=0;t=n+1;sum=0; memset(w,0,sizeof(w)); for(i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); if(d){ add(a,b,0,c); w[a]-=c; w[b]+=c; } else add(a,b,c,c); } for(i=1;i<=n;i++) { if(w[i]>0) { sum+=w[i]; add(s,i,w[i],0); } else add(i,t,-w[i],0); } f=dinic(s,t); index=yong; add(n,1,inf,0); ff=dinic(s,t); if(f+ff!=sum) printf("Impossible "); else { printf("%d ",bian[index^1].w); for(i=0;i<m-1;i++) printf("%d ",bian[i*2].f-bian[i*2].w); printf("%d ",bian[i*2].f-bian[i*2].w); } } return 0; }