#include <cstdio>

using namespace std;
const int INF=2000000000;
int n,m,start,i,j,k,x,y,check,c[50000][50000],cmin[50000],tata[50000],v[50000];

int main()
{
    freopen("bellman-ford.in","r",stdin);
    freopen("bellman-ford.out","w",stdout);

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

    for(i=1;i<=m;++i){

        scanf("%d%d",&x,&y);
        scanf("%d",&c[x][y]);

    }
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j){

            if(c[i][j]==0 && i!=j){

                c[i][j]=INF;

            }

        }
    }

    for(i=1;i<=n;++i){

        cmin[i]=c[start][i];
        tata[i]=start;
    }

    tata[start]=0;
    for(i=1;i<=n;++i){
        check=0;
        for(j=1;j<=n;++j){

            for(k=1;k<=n;++k){

                if(c[j][k]!=INF && j!=k){

                    if(cmin[k]>cmin[j]+c[j][k]){

                        cmin[k]=cmin[j]+c[j][k];
                        tata[k]=j;
                        check=1;

                    }

                }

            }

        }

    }

    if(check==1){printf("Ciclu negativ!");}

    else {
        for(i=1;i<=n;++i){
            if(i!=start){
            k=1;
            v[k]=i;
            while(v[k]!=0){

                v[++k]=tata[v[k-1]];

            }
            printf("drumul minim de la %d la %d are costul %d si urmeaza varfurile:\n",start,i,cmin[i]);
            for(j=k-1;j>=1;--j){

                printf("%d ",v[j]);

            }
            printf("\n");
            }
        }
    }
    return 0;
}