/*CLR, page 605-609*/
/*Bob Weems, Spring 1994*/

#include <stdio.h>

#define maxVertices 20
#define maxEdges (maxVertices*maxVertices)
#define min(x,y) ((x<y) ? x : y)
#define cF(x,y) (capacity[x][y] - flow[x][y])

int n,m;  /*number of vertices, number of edges*/
int s,t;  /*source and sink*/
int capacity[maxVertices][maxVertices];
int height[maxVertices],excessFlow[maxVertices];
int flow[maxVertices][maxVertices];

void readInput()
{
int i,j,tailIn,headIn,capacityIn;

scanf("%d %d",&n,&m);
scanf("%d %d",&s,&t);

for (i=0;i<n;i++)
  for (j=0;j<n;j++)
    capacity[i][j]=0;

for (i=0;i<m;i++)
{
  scanf("%d %d %d",&tailIn,&headIn,&capacityIn);
  capacity[tailIn][headIn]=capacityIn;
}
}

void dumpTables()
{
int i,j;

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

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

initializePreflow()
{
int i,j;

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

for (i=0;i<n;i++)
  for (j=0;j<n;j++)
  flow[i][j]=0;

height[s]=n;

for (i=0;i<n;i++)
  if (capacity[s][i])
  {
    flow[s][i]=capacity[s][i];
    flow[i][s]=(-capacity[s][i]);
    excessFlow[i]=capacity[s][i];
  }
}

void preflowPushLoop()
{
int foundOperation,didPush,i,j,dF,minHeight;

foundOperation=1;
while (foundOperation)
{
  foundOperation=0;
  for (i=0;i<n;i++)
    if (i!=s && i!=t && excessFlow[i]>0)
    {
      didPush=0;
      for (j=0;j<n;j++)
      {
        if (cF(i,j)>0 &&
            height[i]==height[j]+1)
        {
          dF=min(excessFlow[i],cF(i,j));
          printf("debug:  pushing %d units from %d to %d\n",
            dF,i,j);
          flow[i][j]+=dF;
          flow[j][i]=(-flow[i][j]);
          excessFlow[i]-=dF;
          excessFlow[j]+=dF;
          didPush=1;
          foundOperation=1;
          if (excessFlow[i]==0)
            break;
        }
      }
      if (!didPush)
      {
        minHeight=1000;
        for (j=0;j<n;j++)
          if (cF(i,j)>0 && height[j]<minHeight)
          {
            printf("debug:  (%d,%d) changed minHeight to %d\n",
              i,j,height[j]);
            minHeight=height[j];
          }
        printf("debug:  lifting %d from %d to %d\n",
          i,height[i],1+minHeight);
        height[i]=1+minHeight;
        foundOperation=1;
      }
    }
  printf("debug:\n");
  dumpTables();
}
}

main()
{
readInput();
initializePreflow();
printf("debug:  after initialization\n");
dumpTables();
preflowPushLoop();
printf("final result:\n");
dumpTables();
}