#include<iostream>
using namespace std;

int F[102][102];

void
DFS (int Y, int X, int A)
{
  if (F[Y][X] != A)
    return;

  F[Y][X] = 7;

  DFS (Y - 1, X, A);
  DFS (Y, X + 1, A);
  DFS (Y + 1, X, A);
  DFS (Y, X - 1, A);
}

int
main ()
{
  int w, h;
  int xs, ys;
  int xg, yg;
  int n;
  int c, d, x, y;

  while (true)
    {
      cin >> w >> h;
      if (w == 0 && h == 0)
	break;
      cin >> xs >> ys;
      cin >> xg >> yg;
      cin >> n;

      for (int i = 0; i < n; i++)
	{
	  cin >> c >> d >> x >> y;
	  if (d == 0)
	    {
	      for (int a = 0; a < 4; a++)
		{
		  for (int b = 0; b < 2; b++)
		    {
		      F[y + b][x + a] = c;
		    }
		}

	    }
	  else
	    {
	      for (int a = 0; a < 2; a++)
		{
		  for (int b = 0; b < 4; b++)
		    {
		      F[y + b][x + a] = c;
		    }
		}
	    }

	}


      if (F[ys][xs] == 1 || F[ys][xs] == 2 || F[ys][xs] == 3
	  || F[ys][xs] == 4 || F[ys][xs] == 5)
	{
	  DFS (ys, xs, F[ys][xs]);
	}

      if (F[yg][xg] == F[ys][xs])
	{
	  cout << "OK" << endl;
	}
      else
	{
	  cout << "NG" << endl;
	}

    }

  return 0;
}
#include<iostream>
#include<cstdio>
#include<vector>
 
#define INF 999999999
#define ll long long
 
using namespace std;
 
const int MAX_N = 100000;
const int MAX_M = 500000;
 
struct edge
{
    int from;  //?????????
    int to;    //??°??????
    int cost;  //??????
};
 
int d[MAX_N];
edge es[MAX_M];
bool flag;  //???????????????????????????
 
void shortest_path(int n,int m,int s)   //s???????????????????????????????????????????????¢????±???????
{
    int cnt = 0;
    fill(d,d+n,INF);
    d[s] = 0;
    while(true && cnt < n){
        bool update = false;
        for(int i=0;i<m;i++){
            edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if(!update) break;
        cnt++;
    }
    if(cnt == n){
        flag = true;
    }
}
 
int main()
{
    int i,n,m,s;
    cin >> n;  //????????°
    cin >> m;  //?????°
    cin >> s;  //???????????????
    for(int i=0;i<m;i++){
        scanf("%d",&es[i].from);
        scanf("%d",&es[i].to);
        scanf("%d",&es[i].cost);
    }
    flag = false;
    shortest_path(n,m,s);
    if(!flag){
        for(int i=0;i<n;i++){
            if(d[i] == INF){
                cout << "INF\n";
            }else{
                cout << d[i] << "\n";
            }
        }
    }else{
        cout << "NEGATIVE CYCLE\n";
    }
}
