codeforces567E. President and Roads

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 200005
#define maxm 200005
#define inf 4557430888798830399LL
using namespace std;
typedef long long int64;
char ch;
int n,m,s,t,a[maxm],b[maxm],idx,dfn[maxn],low[maxn];
int64 c[maxm],min_road;
int siz,pos[maxn];
struct Heap{
    int64 val;
    int num;
    bool operator <(const Heap b)const{return val<b.val;}
    bool operator >(const Heap b)const{return b<*this;}
    bool operator <=(const Heap b)const{return !(*this>b);}
    bool operator >=(const Heap b)const{return !(*this<b);}
    bool operator ==(const Heap b)const{return (*this<=b)&&(*this>=b);}
    bool operator !=(const Heap b)const{return !(*this==b);}
}heap[maxn],tmp;
struct Map{
    int tot,now[maxn],son[maxm],pre[maxm],val[maxm];
    int64 dist[maxn];
    void put(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}    
}map[3];
bool ok,bo[maxn],road[maxm];
void read(int &x){
    for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch==‘-‘) ok=1;
    for (x=0;isdigit(ch);x=x*10+ch-‘0‘,ch=getchar());
    if (ok) x=-x;
}
void read(int64 &x){
    for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch==‘-‘) ok=1;
    for (x=0;isdigit(ch);x=x*10+ch-‘0‘,ch=getchar());
    if (ok) x=-x;
}
void heap_swap(Heap &a,Heap &b){swap(pos[a.num],pos[b.num]),swap(a,b);}
void up(int son){
    int fa=son>>1;
    while (fa){
        if (heap[fa]<=heap[son]) break;
        heap_swap(heap[fa],heap[son]);
        son=fa,fa>>=1;
    }
}
void down(){
    int fa=1,son=fa<<1;
    while (son<=siz){
        if (son+1<=siz&&heap[son+1]<heap[son]) son++;
        if (heap[fa]<=heap[son]) break;
        heap_swap(heap[fa],heap[son]);
        fa=son,son<<=1;
    }
}
void dijkstra(Map &map,int s){
    siz=n;
    memset(map.dist,63,sizeof(map.dist));
    memset(bo,0,sizeof(bo));
    for (int i=1;i<=n;i++) heap[i].val=inf;
    for (int i=1;i<=n;i++) heap[i].num=i;
    for (int i=1;i<=n;i++) pos[i]=i;
    heap[s].val=0,up(pos[s]);
    for (;;){
        if (heap[1].val==inf||!siz) break;
        int u=heap[1].num;
        bo[u]=true,map.dist[u]=heap[1].val;
        heap_swap(heap[1],heap[siz--]),down();
        for (int p=map.now[u],v=map.son[p];p;p=map.pre[p],v=map.son[p]){
            if (heap[pos[v]].val>map.dist[u]+map.val[p]&&!bo[v])
                heap[pos[v]].val=map.dist[u]+map.val[p],up(pos[v]);
        }
    }
}
void dfs(Map &map,int u,int t){
    dfn[u]=low[u]=++idx;
    for (int p=map.now[u],v=map.son[p];p;p=map.pre[p],v=map.son[p])
        if (!dfn[v]){
            dfs(map,v,p^1),low[u]=min(low[u],low[v]);
            if (low[v]>dfn[u]) road[pos[p>>1]]=1;
        }
        else if (t!=p) low[u]=min(low[u],dfn[v]);
}
int main(){
    read(n),read(m),read(s),read(t);
    for (int i=1;i<=m;i++) read(a[i]),read(b[i]),read(c[i]),map[0].put(a[i],b[i],c[i]),map[1].put(b[i],a[i],c[i]);
    dijkstra(map[0],s),dijkstra(map[1],t),min_road=map[0].dist[t],map[2].tot=1;
    for (int i=1;i<=m;i++) if (map[0].dist[a[i]]+map[1].dist[b[i]]+c[i]==min_road)
        map[2].put(a[i],b[i],c[i]),map[2].put(b[i],a[i],c[i]),pos[map[2].tot>>1]=i;//,cout<<a[i]<<‘ ‘<<b[i]<<endl;
    dfs(map[2],s,-1);
    for (int i=1;i<=m;i++)
        if (map[0].dist[a[i]]+map[1].dist[b[i]]+c[i]==min_road){
            if (road[i]) puts("YES");
            else if (c[i]>1) puts("CAN 1");
            else puts("NO");
        }
        else if (map[0].dist[a[i]]+map[1].dist[b[i]]+c[i]>min_road){
            if (min_road>map[0].dist[a[i]]+map[1].dist[b[i]]+1) printf("CAN %I64d\n",map[0].dist[a[i]]+map[1].dist[b[i]]+c[i]-min_road+1);
            else puts("NO");
        }
        else puts("NO");
    return 0;
}