#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=505;
pair<int,int> g[N][N];
int n,m,start,rear;
int dist[N],cost[N],prec[N],pred[N],sum[N];
bool st[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);


    dist[start]=cost[start]=0;


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

        for(int j=0;j<n;j++)
        {
            if(dist[j]>dist[t]+g[t][j].first)
            {
                pred[j]=t;
                dist[j]=dist[t]+g[t][j].first;
                cost[j]=cost[t]+g[t][j].second;

            }
            else if(dist[j]==dist[t]+g[t][j].first)
            {
                if(cost[j]>cost[t]+g[t][j].second)
                {
                    pred[j]=t;
                    cost[j]=cost[t]+g[t][j].second;


                }

            }
        }


    }
    memset(st,false,sizeof st);

    memset(cost, 0x3f, sizeof cost);
    sum[start]=1;
    dist[start]=cost[start]=0;
     for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=0;j<n;j++)
        {
            if(!st[j]&&(t==-1||cost[t]>cost[j]))
            t=j;
        }
        st[t]=true;

        for(int j=0;j<n;j++)
       {
            if(cost[j]>cost[t]+g[t][j].second)
            {
                prec[j]=t;
                cost[j]=cost[t]+g[t][j].second;
               sum[j]=sum[t]+1;

            }
            else  if(cost[j]==cost[t]+g[t][j].second)
            {
                if(sum[j]>sum[t]+1)
                {
                    prec[j]=t;
                   sum[j]=sum[t]+1;

                }


            }
       }

    }



}

bool check(vector<int>a ,vector<int> b)
{
    if(a.size()!=b.size()) return false;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]!=b[i]) return false;
    }
    return true;
}


void express(vector<int> a)
{
    for(int i=a.size()-1;i>=0;i--)
    {
        cout<<a[i];
        if(i)
        cout<<" -> ";



    }
}


int main()
{
    cin>>n>>m;
    memset(g,0x7f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int a,b,op,c,d;
        cin>>a>>b>>op>>c>>d;
        g[a][b]={c,d};
        if(!op)
        g[b][a]={c,d};

    }
    cin>>start>>rear;
    dijkstra();
    vector<int> resd,resc;

    int now=rear;
    while(now!=start)
    {
        resd.push_back(now);
        now=pred[now];

    }
    resd.push_back(start);
    now=rear;
     while(now!=start)
    {
        resc.push_back(now);
        now=prec[now];

    }
    resc.push_back(start);

    printf("Distance = %d",dist[rear]);

    if(check(resc,resd))  cout<<"; ";
    else 
    {
    cout<<": ";
    express(resd);
    cout<<endl;
  }
    printf("Time = %d: ",cost[rear]);
    express(resc);    

    return 0;
}