#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
#define SOUBOR_VSTUP "skladiste.in"
#define MAXINT 100000
#define MAX_N 500


typedef struct ulicka {
    int kam;
    int delka;
    bool vodic;
} ulicka;

typedef struct krizovatka {
    bool final_lichy;
    int odkud_licha;
    int vzdalenost_licha;
    bool final_sudy;
    int odkud_suda;
    int vzdalenost_suda;
    vector<ulicka> ulicky;
} krizovatka;

int halda_licha[2*MAX_N];
int halda_suda[2*MAX_N];
int halda_licha_velikost=0;
int halda_suda_velikost=0;

krizovatka vrchol[MAX_N];

void halda_licha_vloz(int prvek) {
    int i=halda_licha_velikost;
    halda_licha_velikost++;
    halda_licha[i]=prvek;
    while(i>0 && (vrchol[halda_licha[(i-1)/2]].vzdalenost_licha>vrchol[halda_licha[i]].vzdalenost_licha)) {
        int pomocna=halda_licha[(i-1)/2]; halda_licha[(i-1)/2]=halda_licha[i]; halda_licha[i]=pomocna;
        i=(i-1)/2;
    }
}
void halda_suda_vloz(int prvek) {
    int i=halda_suda_velikost;
    halda_suda_velikost++;
    halda_suda[i]=prvek;
    while(i>0 && (vrchol[halda_suda[(i-1)/2]].vzdalenost_suda>vrchol[halda_suda[i]].vzdalenost_suda)) {
        int pomocna=halda_suda[(i-1)/2]; halda_suda[(i-1)/2]=halda_suda[i]; halda_suda[i]=pomocna;
        i=(i-1)/2;
    }
}
int halda_licha_odeber() {
    int vrat=halda_licha[0];
    halda_licha_velikost--;
    halda_licha[0]=halda_licha[halda_licha_velikost];
    int i=0;
    while(2*i+1<halda_licha_velikost) {
        int j=i;
        if(vrchol[halda_licha[(2*i)+1]].vzdalenost_licha<vrchol[halda_licha[i]].vzdalenost_licha
        && vrchol[halda_licha[(2*i)+2]].vzdalenost_licha<vrchol[halda_licha[i]].vzdalenost_licha) {
            if(vrchol[halda_licha[(2*i)+1]].vzdalenost_licha<vrchol[halda_licha[(2*i)+2]].vzdalenost_licha) j=(2*i)+1;
            else j=(2*i)+2;
        } else if(vrchol[halda_licha[(2*i)+1]].vzdalenost_licha<vrchol[halda_licha[i]].vzdalenost_licha) j=(2*i)+1;
        else if(vrchol[halda_licha[(2*i)+2]].vzdalenost_licha<vrchol[halda_licha[i]].vzdalenost_licha) j=(2*i)+2;
        else break;

        int pomocna=halda_licha[i]; halda_licha[i]=halda_licha[j]; halda_licha[j]=pomocna;
    }
    return vrat;
}
int halda_suda_odeber() {
    int vrat=halda_suda[0];
    halda_suda_velikost--;
    halda_suda[0]=halda_licha[halda_suda_velikost];
    int i=0;
    while(2*i+1<halda_suda_velikost) {
        int j=i;
        if(vrchol[halda_suda[(2*i)+1]].vzdalenost_licha<vrchol[halda_suda[i]].vzdalenost_licha
        && vrchol[halda_suda[(2*i)+2]].vzdalenost_licha<vrchol[halda_suda[i]].vzdalenost_licha) {
            if(vrchol[halda_suda[(2*i)+1]].vzdalenost_licha<vrchol[halda_suda[(2*i)+2]].vzdalenost_licha) j=(2*i)+1;
            else j=(2*i)+2;
        } else if(vrchol[halda_suda[(2*i)+1]].vzdalenost_licha<vrchol[halda_suda[i]].vzdalenost_licha) j=(2*i)+1;
        else if(vrchol[halda_suda[(2*i)+2]].vzdalenost_licha<vrchol[halda_suda[i]].vzdalenost_licha) j=(2*i)+2;
        else break;

        int pomocna=halda_suda[i]; halda_suda[i]=halda_suda[j]; halda_suda[j]=pomocna;
    }
    return vrat;
}

int main() {
    FILE *vstup=fopen(SOUBOR_VSTUP, "r");
    int N, M;
    fscanf(vstup,"%d %d",&N,&M);
    int start,cil;
    fscanf(vstup,"%d %d",&start,&cil);

    for(int i=1;i<=N;i++) {
        vrchol[i].final_lichy=false;
        vrchol[i].vzdalenost_licha=MAXINT;
        vrchol[i].final_sudy=false;
        vrchol[i].vzdalenost_suda=MAXINT;
    }

    for(int i=1;i<=M;i++) {
        int odkud,kam,delka,vodic;
        fscanf(vstup,"%d %d %d %d",&odkud,&kam,&delka,&vodic);
        // a vložíme uličku do seznamu obou křižovatek
        ulicka pomocna1,pomocna2;
        pomocna1.kam=kam;
        pomocna2.kam=odkud;
        pomocna1.delka=pomocna2.delka=delka;
        pomocna1.vodic=pomocna2.vodic=(vodic!=0);
        vrchol[odkud].ulicky.push_back(pomocna1);
        vrchol[kam].ulicky.push_back(pomocna2);
    }

    // máme načtený vstup, teď spustíme upraveného Dijkstru

    vrchol[start].vzdalenost_licha=0;

    halda_licha_vloz(start);
    while(!(vrchol[cil].final_lichy && vrchol[cil].final_sudy)) {
        if(halda_licha_velikost>0) {
            printf("Odebiram vrchol z liche\n");
            int i=halda_licha_odeber();
            if(!vrchol[i].final_lichy) {
                vrchol[i].final_lichy=true;
                for(int j=0;j<vrchol[i].ulicky.size();j++) {
                    ulicka pomocna=vrchol[i].ulicky.at(j);
                    int cesta=pomocna.delka;
                    if(pomocna.vodic) cesta*=2;
                    if(vrchol[pomocna.kam].vzdalenost_suda>vrchol[i].vzdalenost_licha+cesta) {
                        vrchol[pomocna.kam].odkud_suda=i;
                        vrchol[pomocna.kam].vzdalenost_suda=vrchol[i].vzdalenost_licha+cesta;
                        halda_suda_vloz(pomocna.kam);
                    }
                }
            }
        }
        if(halda_suda_velikost>0) {
            printf("Odebiram vrchol ze sude\n");
            int i=halda_suda_odeber();
            if(!vrchol[i].final_sudy) {
                vrchol[i].final_sudy=true;
                for(int j=0;j<vrchol[i].ulicky.size();j++) {
                    ulicka pomocna=vrchol[i].ulicky.at(j);
                    int cesta=pomocna.delka;
                    if(vrchol[pomocna.kam].vzdalenost_licha>vrchol[i].vzdalenost_suda+cesta) {
                        vrchol[pomocna.kam].odkud_licha=i;
                        vrchol[pomocna.kam].vzdalenost_licha=vrchol[i].vzdalenost_suda+cesta;
                        halda_licha_vloz(pomocna.kam);
                    }
                }
            }
        }
    }

    int i=cil;
    printf("Vzdalenost: %d\n%d",min(vrchol[cil].vzdalenost_licha,vrchol[cil].vzdalenost_suda),cil);

    bool licha=false;
    if(vrchol[i].vzdalenost_licha<vrchol[i].vzdalenost_suda) licha=true;
    while(i!=start) {
        if(licha) { i=vrchol[i].odkud_licha; licha=false; }
        else { i=vrchol[i].odkud_suda; licha=true; }
        printf(" %d",i);
    }

    return 0;
}