#include <cmath> using namespace std; #include <numeric> #include <functional> #include <iostream> #include <algorithm> #include <bitset> #include < string> #include <cstring> #include <cstdio> #include <queue> #include < set> // By chyx111 typedef pair< int, int> pii; #define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i) const int MAXN = 128; int G[ MAXN ][ MAXN ], flow[ MAXN ], pnt[ MAXN ]; int add[ MAXN ][ MAXN ]; // E是具体题目的数据，与模板无关 int E[ MAXN*MAXN ][ 3 ]; bitset< MAXN > mk; int oo = 0x0f0f0f0f; int n, m; int augment(){ mk.reset(); memset(flow, 0,( sizeof flow)); flow[ 0] = oo; priority_queue<pii> Q; Q.push( pii(oo, 0) ); mk.reset(); while( !Q.empty() ){ int cur = Q.top().second; Q.pop(); mk[cur] = true; if( cur == n+ 1){ for( int i = cur; i != 0; i = pnt[i] ){ G[pnt[i]][i] -= flow[n+ 1]; G[i][pnt[i]] += flow[n+ 1]; add[pnt[i]][i] += flow[n+ 1]; add[i][pnt[i]] -= flow[n+ 1]; } return flow[n+ 1]; } for( int i = 1; i <= n+ 1; ++i) if( !mk[i] && G[cur][i] && flow[i] < G[cur][i] && flow[i] < flow[cur] ){ flow[i] = min( flow[cur], G[cur][i] ); pnt[i] = cur; Q.push( pii(flow[i], i ) ); } } return 0; } int maxflow(){ int add; int ans = 0; while( add = augment() ){ // cout << "augment: " << add << endl; ans += add; } return ans; } int main() { while(cin >> n >> m){ memset(G, 0,( sizeof G)); memset(add, 0,( sizeof add)); G[ 0][ 1] = oo; G[n][n+ 1] = oo; Rep(i,m){ int a, b, c, d; scanf( " %d%d%d%d ", &a, &b, &c, &d); E[i][ 0] = a; E[i][ 1] = b; E[i][ 2] = c; if(d){ G[ 0][b] += c; G[a][n+ 1] += c; } else{ G[a][b] = G[b][a] = c; E[i][ 2] = 0; } } bool ok = true; int flow = maxflow(); if( count( G[ 0]+ 2, G[ 0]+n+ 1, 0 ) != n- 1) ok = false; if( ok ){ cout << add[ 0][ 1] << endl; Rep(i,m){ if(i) putchar( ' '); printf( " %d ", E[i][ 2] + max(add[E[i][ 0]][E[i][ 1]],add[E[i][ 1]][E[i][ 0]])); } puts( ""); } else{ puts( " Impossible "); } } return 0; }