//就当两题干！！！
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N=510;

int n,m,S,T;
int d1[N][N],d2[N][N];
int dist1[N],dist2[N],pre[N];//d1存放length ，d2存放time ，pre前一个点
bool st[N];

void dijkstra1()
{
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    memset(st, 0, sizeof st);
    dist1[S] = dist2[S] = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 0; j < n; j ++ )
            if (!st[j] && (t == -1 || dist1[t] > dist1[j]))
                t = j;
        st[t] = true;

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

            if (dist1[j] > dist1[t] + d1[t][j])
            {
                dist1[j] = dist1[t] + d1[t][j];
                dist2[j] = dist2[t] + d2[t][j];
                pre[j] = t;
            }
            else if (dist1[j] == dist1[t] + d1[t][j])
            {
                if (dist2[j] > dist2[t] + d2[t][j])
                {
                    dist2[j] = dist2[t] + d2[t][j];
                    pre[j] = t;
                }
            }
        }
    }
}

void dijkstra2()
{
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    memset(st, 0, sizeof st);
    dist1[S] = dist2[S] = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 0; j < n; j ++ )
            if (!st[j] && (t == -1 || dist1[t] > dist1[j]))
                t = j;
        st[t] = true;

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

            if (dist1[j] > dist1[t] + d2[t][j])
            {
                dist1[j] = dist1[t] + d2[t][j];
                dist2[j] = dist2[t] + 1;
                pre[j] = t;
            }
            else if (dist1[j] == dist1[t] + d2[t][j])
            {
                if (dist2[j] > dist2[t] + 1)
                {
                    dist2[j] = dist2[t] + 1;
                    pre[j] = t;
                }
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    memset(d1,0x3f,sizeof d1);
    memset(d2,0x3f,sizeof d2);
    for(int i=0;i<m;i++)
    {
        int a,b,c,d,e;
        cin>>a>>b>>c>>d>>e;
        d1[a][b]=min(d1[a][b],d);
        d2[a][b]=min(d2[a][b],e);
        if(c == 0)
        {
            d1[b][a] = d1[a][b];
            d2[b][a] = d2[a][b];
        }
    }

      cin >> S >> T;

    int dis,time;

    dijkstra1();
    vector<int> path1;
    for (int i = T; i != S; i = pre[i]) path1.push_back(i);
    path1.push_back(S);
    dis=dist1[T];

    dijkstra2();
    vector<int> path2;
    for (int i = T; i != S; i = pre[i]) path2.push_back(i);
    path2.push_back(S);
    time=dist1[T];

      if(path1!=path2)
      {
        printf("Distance = %d: ", dis);
        cout<<path1[path1.size()-1];
        for(int i=path1.size()-2;i>=0;i--) cout<<" -> "<<path1[i];
        cout<<endl;

        printf("Time = %d: ", time);
        cout<<path2[path2.size()-1];
        for(int i=path2.size()-2;i>=0;i--) cout<<" -> "<<path2[i];
        cout<<endl;
      }
      else
      {
        printf("Distance = %d; Time = %d: ", dis, time);
        cout<<path2[path2.size()-1];
        for(int i=path2.size()-2;i>=0;i--) cout<<" -> "<<path2[i];
        cout<<endl;
       } 

      return 0;
 } 


#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N=510;

int n,m,S,T;
int d1[N][N],d2[N][N];  //d1存length  d2存time
int dist1[N],dist2[N],pre[N];//d1存放length ，d2存放time ，pre前一个点
bool st[N];

pair<int,string>dijkstra(int d1[][N],int d2[][N],int type)
{
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    memset(st, 0, sizeof st);
    dist1[S] = dist2[S] = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 0; j < n; j ++ )
            if (!st[j] && (t == -1 || dist1[t] > dist1[j]))
                t = j;
        st[t] = true;

        for (int j = 0; j < n; j ++ )
        {
            int w; //0：最短路径，距离第一关键字，时间第二关键1：最快，时间第一关键字，节点数最少第二
            if(type==0) w=d2[t][j];
            else w=1;
            if (dist1[j] > dist1[t] + d1[t][j])
            {
                dist1[j] = dist1[t] + d1[t][j];
                dist2[j] = dist2[t] + w;
                pre[j] = t;
            }
            else if (dist1[j] == dist1[t] + d1[t][j])
            {
                if (dist2[j] > dist2[t] + w)
                {
                    dist2[j] = dist2[t] + w;
                    pre[j] = t;
                }
            }
        }
    }
    vector<int> path;
    for (int i = T; i != S; i = pre[i]) path.push_back(i);

    pair<int, string> res;
    res.first = dist1[T];
    res.second = to_string(S);
    for (int i = path.size() - 1; i >= 0; i -- )
        res.second += " -> " + to_string(path[i]);
    return res;


}
int main()
{
    cin>>n>>m;
    memset(d1,0x3f,sizeof d1);
    memset(d2,0x3f,sizeof d2);
    for(int i=0;i<m;i++)
    {
        int a,b,c,d,e;
        cin>>a>>b>>c>>d>>e;
        d1[a][b]=min(d1[a][b],d);
        d2[a][b]=min(d2[a][b],e);
        if(c == 0)
        {
            d1[b][a] = d1[a][b];
            d2[b][a] = d2[a][b];
        }
    }

      cin >> S >> T;

      auto A = dijkstra(d1,d2,0);
      auto B = dijkstra(d2,d1,1);

      if (A.second != B.second)
      {
        printf("Distance = %d: %s\n", A.first, A.second.c_str());
        printf("Time = %d: %s\n", B.first, B.second.c_str());
      }
      else
      {
         printf("Distance = %d; Time = %d: %s\n", A.first, B.first, A.second.c_str());
       } 

      return 0;
 }