// Basic preflow-push
// BPW, 10/2002

#include <stdio.h>
#include <stdlib.h>

// Basic Definitions

#define oo 1000000000

// Declarations

int n;  // number of nodes
int e;  // number of edges
struct edge {
  int tail,head,capacity,flow,inverse; 
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge;  // Table indicating first in range of edges with a common tail

int *excessFlow,*height;

int min (int x, int y)
{
return x<y ? x : y;  // returns minimum of x and y
}

// Reading the input file and the main program

int tailThenHead(const void* xin, const void* yin)
/* Used in calls to qsort() and bsearch() for read_input_file() */
{
int result;
edgeType *x,*y;

x=(edgeType*) xin;
y=(edgeType*) yin;
result=x->tail - y->tail;
if (result!=0)
  return result;
else
  return x->head - y->head;
}

void read_input_file()
{
int a,b,c,i,j,numEdges;
edgeType work;
edgeType *ptr;

// read number of nodes and edges
scanf("%d %d",&n,&e);
edgeTab=(edgeType*) malloc(2*e*sizeof(edgeType));
if (!edgeTab)
{
  printf("edgeTab malloc failed\n");
  exit(0);
}
// read edge capacities
numEdges=0;
for (i=0; i<e; i++)
{
  scanf("%d %d %d",&a,&b,&c);
  if (a<0 || a>n-2 || b<1 || b>=n || c<=0)
  {
    printf("Invalid input %d %d %d\n",a,b,c);
    exit(0);
  }
  edgeTab[numEdges].tail=a;
  edgeTab[numEdges].head=b;
  edgeTab[numEdges].capacity=c;
  numEdges++;
  edgeTab[numEdges].tail=b;
  edgeTab[numEdges].head=a;
  edgeTab[numEdges].capacity=0;
  numEdges++;
}

// sort edges
qsort(edgeTab,numEdges,sizeof(edgeType),tailThenHead);
// coalesce duplicates
j=0;
for (i=1; i<numEdges; i++)
  if (edgeTab[j].tail==edgeTab[i].tail
     && edgeTab[j].head==edgeTab[i].head)
     edgeTab[j].capacity+=edgeTab[i].capacity; 
  else
  {
    j++;
    edgeTab[j].tail=edgeTab[i].tail;
    edgeTab[j].head=edgeTab[i].head;
    edgeTab[j].capacity=edgeTab[i].capacity;
  }
e=numEdges=j+1;
// Set inverses
for (i=0; i<numEdges; i++)
{
  work.tail=edgeTab[i].head;
  work.head=edgeTab[i].tail;
  ptr=bsearch(&work,edgeTab,numEdges,sizeof(edgeType),tailThenHead);
  if (ptr==NULL)
  {
    printf("bsearch %d failed\n",i);
    exit(0);
  }
  edgeTab[i].inverse=ptr-edgeTab;  // ptr arithmetic to get subscript
}
// For each vertex as a tail, determine first in range of edgeTab entries
firstEdge=(int*) malloc((n+1)*sizeof(int));
if (!firstEdge)
{
  printf("malloc failed\n");
  exit(0);
}
j=0;
for (i=0; i<n; i++)
{
  firstEdge[i]=j;
  for ( ;
       j<numEdges && edgeTab[j].tail==i;
       j++)
    ;
}
firstEdge[n]=numEdges;
}

void dumpTables()
{
int i;

printf("vertex height excess\n");
for (i=0;i<n;i++)
  printf(" %3d %6d %6d\n",i,height[i],excessFlow[i]);

printf(" tail head capacity    flow\n");
for (i=0;i<e;i++)
  if (edgeTab[i].capacity>0)
    printf(" %3d  %3d %8d %7d\n",edgeTab[i].tail,edgeTab[i].head,
      edgeTab[i].capacity,edgeTab[i].flow);
}

initializePreflow()
{
int i,j;

for (i=0;i<n;i++)
{
  height[i]=0;
  excessFlow[i]=0;
}

for (i=0;i<e;i++)
  edgeTab[i].flow=0;

height[0]=n;

for (i=firstEdge[0];i<firstEdge[1];i++)
  if (edgeTab[i].capacity>0)
  {
    edgeTab[i].flow=edgeTab[i].capacity;
    edgeTab[edgeTab[i].inverse].flow=(-edgeTab[i].capacity);
    excessFlow[edgeTab[i].head]=edgeTab[i].capacity;
    excessFlow[0]-=edgeTab[i].capacity;
  }
}

int preflowPushLoop()
{
int i,j,k,dF,minHeight;
int *fifo,*inQueue,tail=0,head=0;

fifo=(int*) malloc((n+1)*sizeof(int));
inQueue=(int*) malloc(n*sizeof(int));
if (!fifo || !inQueue)
{
  printf("fifo/inQueue not allocated\n");
  exit(0);
}
for (i=0;i<n;i++)
  inQueue[i]=0;
inQueue[0]=inQueue[n-1]=1;  // Source and sink are never actually queued!
for (i=firstEdge[0];i<firstEdge[1];i++)
  if (edgeTab[i].capacity>0 && edgeTab[i].head<n-1)
  {
    fifo[tail]=edgeTab[i].head;
    tail=(tail==n) ? 0 : tail+1;
    inQueue[edgeTab[i].head]=1;
  }

while (tail!=head)
{
  i=fifo[head];
  head=(head==n) ? 0 : head+1;
  inQueue[i]=0;
  while (1)
  {
    minHeight=oo;
    for (k=firstEdge[i];k<firstEdge[i+1];k++)
    {
      j=edgeTab[k].head;
      if (edgeTab[k].capacity-edgeTab[k].flow>0)
        if (height[i]==height[j]+1)
        {
          dF=min(excessFlow[i],edgeTab[k].capacity-edgeTab[k].flow);
          //printf("debug: pushing %d units from %d to %d\n",dF,i,j);
          edgeTab[k].flow+=dF;
          edgeTab[edgeTab[k].inverse].flow=(-edgeTab[k].flow);
          excessFlow[i]-=dF;
          excessFlow[j]+=dF;
          if (!inQueue[j])
          {
            fifo[tail]=j;
            tail=(tail==n) ? 0 : tail+1;
            inQueue[j]=1;
          }
          if (excessFlow[i]==0)
            break;
        }
        else if (height[j]<minHeight)
          minHeight=height[j];
    }
    if (excessFlow[i]>0)
    {
      //printf("debug: lifting %d from %d to %d\n", i,height[i],1+minHeight);
      height[i]=1+minHeight;
    }
    else
      break;
  }
/*
  printf("debug:\n");
  dumpTables();
*/
}
free(fifo);
free(inQueue);
return excessFlow[n-1];
}

int main()
{
int i,j;

read_input_file();
excessFlow=(int*) malloc(n*sizeof(int));
height=(int*) malloc(n*sizeof(int));
if (!excessFlow || !height)
{
  printf("malloc failed\n");
  exit(0);
}
initializePreflow();
//dumpTables();
printf("total flow is %d\n",preflowPushLoop());
if (n<=20)
{
  printf("flows along edges:\n");
  for (i=0; i<e; i++)
    if (edgeTab[i].flow>0)
      printf("%d->%d has %d\n",edgeTab[i].tail,
       edgeTab[i].head,edgeTab[i].flow);
}
free(height);
free(excessFlow);
free(edgeTab);
free(firstEdge);
return 0;
}