0][100],d[100];
int n;//nr de intersectii
ifstream f("1.in");
void citire()
{
    int i,j;
    f>>n>>m;
    f>>iplecare>>ifinal;
    vp=iplecare;
    for(i=1;i<=m;i++)
    {f>>x>>y>>z;
     c[x][y]=z;
    }
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i!=j&&c[i][j]==0)
    c[i][j]=infinit;
}

void drum_initial()
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(i!=vp&&c[vp][i]!=infinit)
            p[i]=vp;
        d[i]=c[vp][i];
    }
}



void drum(int i)
{if(p[i]==0)
cout<<vp<<" ";
else{drum(p[i]);
    cout<<i<<" ";
}
}
void afisare()
{ int i;
if(d[ifinal]!=infinit)
    {
        cout<<"distanta min pt vf "<<ifinal<<" = "<<d[ifinal];
        cout<<" drumul este ";
        drum(ifinal);
        cout<<endl;
    }
else cout<<"nu exista drum";
}



void Dijkstra()
{ int i,j,k;
    s[vp]=1;
    for(i=1;i<=n-1;i++)
    {
       int minim=infinit;
        for(j=1;j<=n;j++)
            if(s[j]==0&&d[j]<minim)
        {
            minim=d[j];
            k=j;}
            s[k]=1;
            for(j=1;j<=n;j++)
                if(s[j]==0 && d[j]>d[k]+c[k][j])
            {
                d[j]=d[k]+c[k][j];
                p[j]=k;            }

    }
}

int main()
{
    citire();
    drum_initial();
    Dijkstra();
    afisare();
}