#include<fstream>
#define NMAX 102

using namespace std;

ifstream fin("bf.in");
ofstream fout("bf.out");

int n, m, start;
int C[NMAX][NMAX], M[NMAX], tata[NMAX], cmin[NMAX];

void citire();
void initializare();
void bf();
void afisare();

int main()
{

    citire();
    bf();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i, x, y, j, cost;
    fin>>n>>m>>start;
    for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++) C[i][j]=102;
            C[i][i]=0;
        }
    for(i=1; i<=n; i++)
        {
            fin>>x>>y>>cost; C[x][y]=cost;
        }
}

void initializare()
{
    int i;
    M[start]=1;
    for(i=1; i<=n; i++)
        {
            cmin[i]=C[start][i];
            tata[i]=start;
        }
    tata[start]=0;
}

int minim()
{
    int res=103, vfmin=0, i;
    for(i=1; i<=n; i++)
    {
        if(cmin[i]<res&&M[i]==0)
        {
            res=cmin[i]; vfmin=i;
        }
    }
    M[vfmin]=1;
    return vfmin;
}

void bf()
{
    int x, op, y;
    for(y=1; y<=n; y++)
    {
        op=0;
        for(x=1; x<=n; x++)
            if(cmin[y]>cmin[x]+C[x][y])
            {
                cmin[y]=cmin[x]+C[x][y];
                tata[y]=x; op=1;
            }
    }
    if(op) fout<<"Nu exista solutie";
    else afisare();


}

void drum(int i)
{
    if(tata[i]!=0)
      {
          drum(tata[i]);
          fout<<i<<' ';
      }
   else fout<<i<<' ';
}


void afisare()
{
    int i;
    for(i=1; i<=n&&i!=start; i++)
        if((cmin[i]==NMAX+1)||(cmin[i]<0)) fout<<"Nu exista drum de la "<<start<<" la "<<i<<'\n';
        else fout<<"Costul minim de la "<<start<<" la "<<i<<" este "<<cmin[i]<<'\n';
}