#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define MAXN 1111

 #define inf 1<<30

 struct Edge{

     int v,w;

     Edge(int vv,int ww):v(vv),w(ww){};

 };

 int dist[MAXN][MAXN];//走到点i，路程长度mod k余数为j的最短路程

 char num[MAXN];

 int n,m,s,k,min_len,pos;

 vector<vector<Edge> >G;

 void dfs(int u,int len)

 {

     if(len%k==&&num[u]=='P'){

         if(len<min_len){

             min_len=len,pos=u;

         }else if(len==min_len){

             pos=min(pos,u);

         }

         return ;

     }

     for(int i=;i<G[u].size();i++){

         int v=G[u][i].v,w=G[u][i].w;

         if(dist[v][(len+w)%k]==-||dist[v][(len+w)%k]>(len+w)){

             dist[v][(len+w)%k]=len+w;

             dfs(v,len+w);

         }

     }

 }

 int main()

 {

     int _case,u,v,w,t=;

     scanf("%d",&_case);

     while(_case--){

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

         scanf("%s",num+);

         G.clear();

         G.resize(n+);

         while(m--){

             scanf("%d%d%d",&u,&v,&w);

             G[u].push_back(Edge(v,w));

         }

         memset(dist,-,sizeof(dist));

         min_len=inf;

         dfs(s,);

         if(min_len==inf){

             printf("Case %d: -1 -1\n",t++);

         }else

             printf("Case %d: %d %d\n",t++,min_len,pos);

     }

     return ;

 }