1 //140MS    600K    1953 B    C++
 2 #include<iostream>
 3 #include<queue>
 4 #define N 1005
 5 #define inf 0x3fffffff
 6 using namespace std;
 7 struct node{
 8     int v,h,d;
 9     int next;
10 }edge[20*N];
11 vector<node>V[N];
12 int d[N];
13 int vis[N];
14 int n,s,e;
15 int head[N],edgenum;
16 void addedge(int u,int v,int h,int d)
17 {
18     edge[edgenum].v=v;
19     edge[edgenum].h=h;
20     edge[edgenum].d=d;
21     edge[edgenum].next=head[u];
22     head[u]=edgenum++;
23 }
24 void spfa(int s,int maxh)
25 {
26     for(int i=0;i<=n;i++) 
27        d[i]=inf;
28     memset(vis,0,sizeof(vis));
29     queue<int>Q;
30     d[s]=0;
31     Q.push(s);
32     vis[s]=1;
33     while(!Q.empty()){
34         int u=Q.front();
35         Q.pop();
36         vis[u]=0;
37         for(int i=head[u];i!=-1;i=edge[i].next){
38             int v=edge[i].v;
39             int h=edge[i].h;
40             int w=edge[i].d;
41             if(d[v]>d[u]+w && h>=maxh){
42                 d[v]=d[u]+w;
43                 if(!vis[v]){
44                     Q.push(v);
45                     vis[v]=1;
46                 }
47             }
48         }
49     } 
50 }
51 int main(void) 
52 {
53     int m,a,b,h,c,k=1;
54     while(scanf("%d%d",&n,&m)!=EOF && (n+m))
55     {
56         if(k!=1) printf("\n");
57         memset(head,-1,sizeof(head));
58         for(int i=0;i<=n;i++)
59             V[i].clear();
60         edgenum=0;
61         for(int i=0;i<m;i++){
62             scanf("%d%d%d%d",&a,&b,&h,&c);
63             if(h==-1) h=inf;
64             addedge(a,b,h,c);
65             addedge(b,a,h,c);
66         }
67         scanf("%d%d%d",&s,&e,&h);
68         printf("Case %d:\n",k++);
69         int ans=inf;
70         int l=0,r=h;
71         while(l<r){
72             int mid=(l+r+1)>>1;
73             spfa(s,mid);
74             if(d[e]!=inf){
75                 l=mid;ans=d[e];
76             }else r=mid-1;
77         }
78         if(ans!=inf){
79             printf("maximum height = %d\n",r);
80             printf("length of shortest route = %d\n",ans);
81         }else printf("cannot reach destination\n");
82     }
83     return 0;
84 }