1 #include <iostream>  2 #include <cstdlib>  3 #include <cstring>  4 #include <cstdio>  5 #include <queue>  6 const int inf = 1 << 30 , N = 200 + 11 ;  7 using namespace std ;  8 int head[N] , n , m , dis[N] , mark[N] , cnt , s , t , ans ;  9 struct id 10 { 11     int nxt , to  , val , vol ; 12 } e[80011] ; 13 queue < int > Q ; 14  15  16 inline void Init( ) 17 { 18     freopen( "NSOOJ#10399.in" , "r" , stdin ) ; 19     freopen( "NSOOJ#10399.out" , "w" , stdout )   ; 20 } 21  22  23 void add( int a , int b  , int c , int d  ) 24 { 25     e[++cnt].nxt = head[a] , e[cnt].to = b ; 26     e[cnt].val = c , e[cnt].vol = d ; head[a] = cnt ; 27 } 28  29 int read(  ) { 30     char ch = getchar(  ) ; int ret = 0 , k = 1 ; 31     while( ch < ‘0‘ || ch > ‘9‘ ) { if( ch == ‘-‘ ) k = -1 ; ch = getchar(  ) ; } 32     while( ch >= ‘0‘ && ch <= ‘9‘ ) ret = ret * 10 + ch - ‘0‘ , ch = getchar(  ) ; 33     return ret * k ; 34 } 35  36  37 void input( ) 38 { 39     n = read( ) , m = read( ) ; cnt = -1 ;  40     s = 1  , t = n  ; int a, b , c , d ; 41     memset( head , -1 , sizeof(head) ) ; 42     int maxn = 0 ; 43     for( int x = 1 ; x <= m ; x ++ ) 44     { 45         a = read( ) , b = read( ) , c = read( ) , d = read( ) ; 46         add( a , b , c , d ) ; 47         add( b , a , 0 , 0-d ) ;  48     } 49  50 } 51  52  53 bool spfa(  ) 54 { 55     memset( mark , 0  , sizeof( mark ) ) ; 56     for( int i = 0 ; i <= t ; i++ ) dis[i] = inf ; 57     dis[t] = 0 , mark[t] = 1 ; Q.push( t ) ; 58     while( !Q.empty( ) ) 59     { 60         int u = Q.front( ) ; Q.pop( ) ; 61         for( int i = head[u] ;~i ; i = e[i].nxt ) 62         { 63             int v = e[i].to ; 64             if( e[i^1].val && dis[u] + e[i^1].vol < dis[v] ) 65             { 66                 dis[v] = dis[u] + e[i^1].vol ; 67                 if( !mark[v] ) 68                 { 69                     mark[v] = 1 ; 70                     Q.push( v ) ; 71                 } 72             } 73         } 74         mark[u] = 0 ; 75     } 76     return dis[s] != inf ; 77 } 78  79  80 int dfs( int u , int f ) 81 { 82     mark[u] = 1 ; 83     if( u == t ) return f ; 84     int w , used = 0 ; 85     for( int i = head[u] ; ~i ; i = e[i].nxt ) 86     { 87         int v = e[i].to ;//cout<<u<<" "<<v<<endl;  88         if( dis[v] == dis[u] - e[i].vol && e[i].val > 0 && !mark[v] ) 89         { 90             w = f - used ; 91             w = dfs( v , min( w , e[i].val ) ) ; 92             ans += w * e[i].vol ; 93             e[i].val -= w , e[i^1].val += w  , used += w ; 94             if( used == f ) return f; 95         } 96     } 97     return used ; 98 } 99 100 101 void zkw(  )102 {103     int sum = 0 ;104     while( spfa(  ) )105     {106         mark[t] = 1 ;107         while( mark[t] )108         {109             memset( mark , 0 , sizeof(mark) ) ;110             sum += dfs( 1 , inf ) ;111         }112     }113     printf( "%d %d\n" , sum , ans ) ;114 }115 116 117 118 119 int main (  )120 {121 //    Init( ) ;122     input( ) ;123     zkw( ) ;124 //    fclose( stdin ) ;125 //    fclose( stdout ) ;126     return 0 ;127 }