http://acm.hdu.edu.cn/showproblem.php?pid=2437
//1364284 2009-05-13 20:11:33 Accepted 2437 187MS 4444K 1362 B C++ no way 
#include <iostream>
#include <vector>
using namespace std;

const int N = 1004;

typedef struct 
{
    int vex;
    int cost;
}node;

vector<node> vv[N];

int ans, e;
char path[N];
int num[N][N];//num[i][j]表示走到i结点花费mod K 的最小值
int n, m, s, k;
int pcnt;

void init()
{
    for(int i = 1; i <= n; i++)
        vv[i].clear();
    ans = e = -1;
    memset(num, -1, sizeof(num));
}

void make_graph()
{
    int a, b, cost;
    node cc;

    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &cost);

        cc.vex = b; cc.cost = cost;
        vv[a].push_back(cc);
       // follows the tunnels you can not go back to the starting burrow.
        //表示单向图
       // cc.vex = a;
        //vv[b].push_back(cc);
    }
}

void dfs(int v,int costs)
{    
    int i,j,p,t;
    if(path[v] =='P' && costs % k == 0 && (ans ==-1 || ans > costs || (ans == costs && v < e)))
    {
        ans = costs;
        e = v;
    }
    j = vv[v].size();
    if(!j)
        return ;    
    for(i=0;i<j;i++)
    {
        p = vv[v][i].vex;
        t = vv[v][i].cost + costs;
        if(num[p][t%k] == -1 || num[p][t%k] > t)
        {
            num[p][t%k] = t;
            dfs(p,t);
        }
    }
}

int main()
{
    int T,i, kk;
    scanf("%d", &T);
    for(i = 1; i <= T; i++)
    {
        scanf("%d%d%d%d", &n, &m, &s, &k);
        getchar();
        scanf("%s", path + 1);
        init();
        make_graph();
        dfs(s,0 );
        cout<<"Case "<<i<<": "<<ans<<" "<<e<<endl;
    }
    return 0;
}