//BermanFloyd
#include<iostream>
#include<fstream>
#define infinit 10000
using namespace std;
void citire(int a[100][100],int &n)
{int m,i,x,y,j,z;
ifstream f("poveste2.in");
f>>n>>m;
for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if (i==j)
        a[i][j]=0;
    else a[i][j]=infinit;

for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=z;
    }
}
int BellmanFord(int a[100][100],int n,int x,int pred[100],int d[100])
{int i,j,k,ok;
    for (i=1;i<=n;i++)
        {
            pred[i]=0;
            d[i]=infinit;
        }
    d[x]=0;
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    for (k=1;k<=n;k++)
        if (d[j]!=infinit && a[i][j]!=infinit)
            if (d[k]>d[j]+a[j][k])
                {
                    d[k]=d[j]+a[j][k];
                    pred[k]=j;
                }

    for (j=1;j<=n;j++)
    for (k=1;k<=n;k++)
        if (d[k]>d[j]+a[j][k])
            return 0;

        return 1;
}
void afisare(int a[100][100],int n)
{for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        cout<<a[i][j]<<"   ";
        cout<<'\n';
    }
}
int main()
{
int a[100][100],n,i,pred[100],d[100],x;
citire(a,n);
cin>>x;
if (BellmanFord(a,n,x,pred,d))
    for (i=1;i<=n;i++)
        cout<<d[i]<<" ";
    else
        cout<<"circuit negativ";
}