There is a funny car racing in a city with n junctions and m directed roads.
The funny part is: each road is open and closed periodically. Each road
is associate with two integers (a, b), that means the road will be open
for a seconds, then closed for b seconds, then open for a seconds... All
these start from the beginning of the race. You must enter a road when
it's open, and leave it before it's closed again.
Your goal is to drive from junction s and arrive at junction t as early
as possible. Note that you can wait at a junction even if all its
adjacent roads are closed.

There
will be at most 30 test cases. The first line of each case contains
four integers n, m, s, t (1<=n<=300, 1<=m<=50,000,
1<=s,t<=n). Each of the next m lines contains five integers u, v,
a, b, t (1<=u,v<=n, 1<=a,b,t<=10⁵), that means
there is a road starting from junction u ending with junction v. It's
open for a seconds, then closed for b seconds (and so on). The time
needed to pass this road, by your car, is t. No road connects the same
junction, but a pair of junctions could be connected by more than one
road.

For each test case, print the shortest time, in seconds. It's always possible to arrive at t from s.

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int INF = ;

int n,m;

struct Edge{

    int v,a,b,t,next;

}edge[];

int tot;

int head[];

void addEdge(int u,int v,int a,int b,int t,int &k){

    edge[k].v = v,edge[k].a = a,edge[k].b = b,edge[k].t = t,edge[k].next = head[u],head[u]=k++;

}

void init(){

    memset(head,-,sizeof(head));

    tot = ;

}

int low[];

bool vis[];

int dijsktra(int s,int t){

    memset(vis,false,sizeof(vis));

    for(int i=;i<=n;i++){

        low[i] = INF;

    }

    low[s] = ;

    vis[s] = true;

    for(int i=;i<n;i++){

        int MIN = INF;

        for(int j=;j<=n;j++){

            if(low[j]<MIN&&!vis[j]){

                MIN = low[j];

                s = j;

            }

        }

        vis[s] = true;

        for(int k=head[s];k!=-;k=edge[k].next){

            int v = edge[k].v,a=edge[k].a,b = edge[k].b,tim = edge[k].t ;

            if(a>=tim){

                int t0 = low[s]%(a+b);

                if(t0+tim<=a) low[v] = min(low[s]+tim,low[v]);

                else low[v] = min(low[s]+a+b-t0+tim,low[v]);

            }

        }

    }

    return low[t];

}

int main()

{

    int s,t,cas=;

    while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF){

        init();

        for(int i=;i<=m;i++){

            int u,v,a,b,t;

            scanf("%d%d%d%d%d",&u,&v,&a,&b,&t);

            addEdge(u,v,a,b,t,tot);

        }

        printf("Case %d: %d\n",cas++,dijsktra(s,t));

    }

    return ;

}