#include<bits/stdc++.h>
using namespace std;
const int N = 510;
bool st[N],st1[N];
int n,m,S, T; //起点和终点路口编号
int dist[N]; //长度
int d[N][N],c[N][N];//d是长度, c是时间
int cnt[N]; //统计路口个数
int pre1[N],pre2[N];
int sum[N],num[N];
// 时间之和 , 经过路口个数
void dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;sum[S] = 0;
for(int i = 0; i< n; i++){
int t = -1;
for( int j =0; j< n; j++){
if(!st[j] &&(t == -1 || dist[j]<dist[t]))
t = j;
}
st[t] =true;
for(int j = 0 ;j < n; j++){
if( dist[j] > dist[t] + d[t][j]){
dist[j] = dist[t] +d[t][j];//长度更新
sum[j] =sum[t] + c[t][j]; //时间更新
pre1[j] = t;
}
else if(dist[j] == dist[t] + d[t][j] && sum[j] > sum[t] + c[t][j]){
sum[j] = sum[t] +c[t][j];
pre1[j] = t;
}
}
}
}
void dijkstra1(){
memset(sum, 0x3f, sizeof sum);
sum[S] = 0;cnt[S]=1;
for(int i = 0; i< n; i++){
int t = -1;
for( int j =0; j< n; j++){
if(!st1[j] &&(t == -1 || sum[j]<sum[t]))
t = j;
}
st1[t] =true;
for(int j = 0 ;j < n; j++){
if( sum[j] > sum[t] + c[t][j]){
sum[j] = sum[t] +c[t][j];//长度更新
cnt[j] =cnt[t]+1;
pre2[j] = t;
}
else if(sum[j] == sum[t] + c[t][j] && cnt[j] > cnt[t] + 1){
cnt[j] =cnt[t] +1;
pre2[j] = t;
}
}
}
}
int main(){
memset(d, 0x3f, sizeof d);
memset(c, 0x3f, sizeof c);
cin >> n >> m;
while(m--){ //m个街道
int a ,b, flag, length , time1;
cin >> a >> b>> flag >> length >>time1;
if(flag == 1)
d[a][b] = min(d[a][b],length),c[a][b] =min(c[a][b],time1);
else d[a][b] = d[b][a] = min(d[a][b],length),c[a][b]=c[b][a] =min(c[a][b],time1);
}
cin >> S >> T;
dijkstra();
vector<int> path1;
for(int i = T; i!=S; i =pre1[i]) path1.push_back(i);
dijkstra1();
vector<int> path;
for(int i = T; i!=S; i =pre2[i]) path.push_back(i);
if(path1 == path){
printf("Distance = %d; Time = %d: ",dist[T],sum[T]);
cout<<S;
for(int i =path1.size() -1; i>=0 ;i--) cout<<" -> "<<path1[i];
cout<<endl;
}
else{
printf("Distance = %d: ",dist[T]);
cout<<S;
for(int i =path1.size() -1; i>=0 ;i--) cout<<" -> "<<path1[i];
cout<<endl;
printf("Time = %d: ",sum[T]);
cout<<S;
for(int i =path.size() -1; i>=0 ;i--) cout<<" -> "<<path[i];
cout<<endl;
}
}