1:  /**

   2:  search the longest path , just jude whether there are a positve cycle.

   3:  

   4:  */

   5:   

   6:  #include <queue>

   7:  #include <iostream>

   8:  #include <string.h>

   9:  #include <stdio.h>

  10:  using namespace std;

  11:  #define V 3000      // vertex

  12:  #define E 1500      // edge

  13:  #define INF 1000000.0f

  14:   

  15:  struct node

  16:  {

  17:      int v, next;

  18:      double R,C,w;

  19:  }pnt[E];

  20:   

  21:  int head[V];

  22:  double  dis[V];

  23:  bool vis[V];

  24:  int  cnt[V];          // the num of the operation of push to Quque. negatvie cycle.

  25:  int e = 0;            // the index of the edge

  26:  int N ;               // the num of the vertex.

  27:  int M ;               // the num of edges

  28:  int src, sink;

  29:  double val;

  30:  void addedge(int  u, int v, double R, double C)

  31:  {

  32:      pnt[e].v = v; pnt[e].w= 0;

  33:      pnt[e].R = R; pnt[e].C = C;

  34:      pnt[e].next = head[u]; head[u] = e++;

  35:  }

  36:  void SPFA_init()

  37:  {

  38:      e=0;

  39:      memset(head, -1,sizeof(head));

  40:      memset(vis, 0 ,sizeof(vis));

  41:      memset(cnt, 0 ,sizeof(cnt));

  42:      for(int i=0; i<=N; i++) dis[i] = 0;

  43:  }

  44:  int SPFA()

  45:  {

  46:      queue<int> Q;

  47:      Q.push(src); vis[src] = 1; dis[src] = val; ++cnt[src]; 

  48:      while(!Q.empty()) 

  49:      {

  50:          int u = Q.front(); Q.pop();  vis[u] = 0;

  51:          for(int i=head[u]; i!=-1; i=pnt[i].next)

  52:          {

  53:              int v = pnt[i].v;

  54:              pnt[i].w = (dis[u] - pnt[i].C)*pnt[i].R - dis[u];

  55:              //cout<<u<<" to "<<v<<" "<<pnt[i].w<<endl;

  56:              if( dis[v] < dis[u] + pnt[i].w  )

  57:              {

  58:                  dis[v] = dis[u] + pnt[i].w;

  59:                  //cout<<u<<" to "<<v<<"  "<<pnt[i].w<<" "<<dis[v]<<endl;

  60:                  if(!vis[v]) { Q.push(v); vis[v] = 1;}

  61:                  if( ++cnt[v] > N) return -1; // negative cycle.

  62:              }

  63:          }

  64:      }

  65:      return 1;

  66:      //if(dis[sink] == INF) return -2;          // can't from src to sink. 

  67:      //return dis[sink];

  68:  }

  69:   

  70:  int main()

  71:  {

  72:      freopen("1860.txt","r",stdin);

  73:      scanf("%d%d", &N , &M);

  74:   

  75:      scanf("%d", &src);

  76:      //cout<<src<<endl;

  77:      scanf("%lf", &val);

  78:      //cout<<val<<endl;

  79:      SPFA_init();

  80:      for(int i=0; i<M; i++)

  81:      {

  82:          int a, b; double Rab, Cab, Rba,Cba;

  83:          scanf("%d%d", &a, &b);

  84:          scanf("%lf%lf", &Rab, &Cab);

  85:          scanf("%lf%lf", &Rba, &Cba);

  86:          addedge(a, b,Rab, Cab);

  87:          addedge(b,a,Rba, Cba);

  88:          //cout<<Rab<<" "<<Cab<<" "<<Rba<<" "<<Cba<<endl;

  89:      }

  90:      int ret = SPFA();

  91:      if(ret == -1)  cout<<"YES"<<endl;

  92:      else cout<<"NO"<<endl;

  93:      return 0;

  94:  }