#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<algorithm>

using namespace std;

int n,m;

int st,en;

struct Edge

{

    int u,v,len,time;

}e[+];

int tot=;

vector<int>g[];

int Dis[],Tim[];

bool flag[];

int ans_len,ans_time,ans_sz,ans_count;

int path[],ans_path[];

vector<int>p1,p2;

int Distance,Time;

void addedge(int u,int v,int len,int time)

{

    e[tot].u=u; e[tot].v=v; e[tot].len=len; e[tot].time=time;

    g[u].push_back(tot++);

}

void SPFA(int s)

{

    queue<int>Q;

    memset(flag,,sizeof flag);

    for(int i=;i<=n;i++) Dis[i]=;

    Q.push(s); flag[s]=; Dis[s]=;

    while(!Q.empty())

    {

        int head=Q.front(); Q.pop(); flag[head]=;

        for(int i=;i<g[head].size();i++)

        {

            int id=g[head][i];

            if(Dis[head]+e[id].len<Dis[e[id].v])

            {

                Dis[e[id].v]=Dis[head]+e[id].len;

                if(flag[e[id].v]==)

                {

                    flag[e[id].v]=;

                    Q.push(e[id].v);

                }

            }

        }

    }

    memset(flag,,sizeof flag);

    for(int i=;i<=n;i++) Tim[i]=;

    Q.push(s); flag[s]=; Tim[s]=;

    while(!Q.empty())

    {

        int head=Q.front(); Q.pop(); flag[head]=;

        for(int i=;i<g[head].size();i++)

        {

            int id=g[head][i];

            if(Tim[head]+e[id].time<Tim[e[id].v])

            {

                Tim[e[id].v]=Tim[head]+e[id].time;

                if(flag[e[id].v]==)

                {

                    flag[e[id].v]=;

                    Q.push(e[id].v);

                }

            }

        }

    }

}

void dfs1(int x,int len,int time,int dep)

{

    if(len>ans_len) return;

    if(x==en)

    {

        if(len<ans_len)

        {

            ans_len=len;

            ans_time=time;

            ans_sz=dep;

            for(int i=;i<dep;i++)

                ans_path[i]=path[i];

        }

        else if(len==ans_len)

        {

            if(time<ans_time)

            {

                ans_time=time;

                ans_sz=dep;

                for(int i=;i<dep;i++)

                    ans_path[i]=path[i];

            }

        }

        return;

    }

    for(int i=;i<g[x].size();i++)

    {

        int id=g[x][i];

        path[dep]=e[id].v;

        if(Dis[x]+e[id].len>Dis[e[id].v]) continue;

        dfs1(e[id].v,len+e[id].len,time+e[id].time,dep+);

    }

}

void dfs2(int x,int time,int count,int dep)

{

    if(time>ans_time) return;

    if(x==en)

    {

        if(time<ans_time)

        {

            ans_time=time;

            ans_count=count;

            ans_sz=dep;

            for(int i=;i<dep;i++)

                ans_path[i]=path[i];

        }

        else if(time==ans_time)

        {

            if(count<ans_count)

            {

                ans_count=count;

                ans_sz=dep;

                for(int i=;i<dep;i++)

                    ans_path[i]=path[i];

            }

        }

        return;

    }

    for(int i=;i<g[x].size();i++)

    {

        int id=g[x][i];

        path[dep]=e[id].v;

        if(Tim[x]+e[id].time>Tim[e[id].v]) continue;

        dfs2(e[id].v,time+e[id].time,count+,dep+);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        int u,v,f,len,time;

        scanf("%d%d%d%d%d",&u,&v,&f,&len,&time);

        addedge(u,v,len,time);

        if(f==) addedge(v,u,len,time);

    }

    scanf("%d%d",&st,&en);

    SPFA(st);

    for(int i=;i<=n;i++) flag[i]=;

    ans_len=;

    ans_time=; flag[st]=;

    dfs1(st,,,);

    Distance = ans_len;

    p1.push_back(st);

    for(int i=;i<ans_sz;i++) p1.push_back(ans_path[i]);

    for(int i=;i<=n;i++) flag[i]=;

    ans_time=;

    ans_count=; flag[st]=;

    dfs2(st,,,);

    Time=ans_time;

    p2.push_back(st);

    for(int i=;i<ans_sz;i++) p2.push_back(ans_path[i]);

    bool fail=;

    if(p1.size()!=p2.size()) fail=;

    else {

        for(int i=;i<p1.size();i++)

            if(p1[i]!=p2[i]) fail=;

    }

    if(fail==)

    {

        printf("Distance = %d; Time = %d: ",Distance,Time);

        for(int i=;i<p1.size();i++)

        {

            printf("%d",p1[i]);

            if(i<p1.size()-) printf(" -> ");

            else printf("\n");

        }

    }

    else

    {

        printf("Distance = %d: ",Distance);

        for(int i=;i<p1.size();i++)

        {

            printf("%d",p1[i]);

            if(i<p1.size()-) printf(" -> ");

            else printf("\n");

        }

        printf("Time = %d: ",Time);

        for(int i=;i<p2.size();i++)

        {

            printf("%d",p2[i]);

            if(i<p2.size()-) printf(" -> ");

            else printf("\n");

        }

    }

    return ;

}