/**
Algoritmul lui Bellman Ford
se citeste un graf orientat cu N varfuri si M arce cu costuri si apoi
un varf de pornire s.
Aplicati Algoritmul lui Bellman Ford pt nodul s
*/

#include <fstream>
#include <vector>
#include <deque>
#define INF 0x7f7f7f7f
#define pb push_back
#define pf pop_front

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct vecin
{
    int j, c;
};
vector <vecin> V[100000];
int N, M;
int P[100000], D[100000];
deque <int> Q;
int s;
void citire()
{
    fin >> N >> M;
    int x;
    vecin y;
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y.j >> y.c;
        V[x].pb(y);
    }
    fin >> s;
}

int BellmanFord(int s)
{
    for(int i = 1; i <= N; i++)
        D[i] = INF;
    D[s] = 0;
    Q.pb(s);
    int k;
    while(!Q.empty())
    {
        k = Q.front();
        Q.pf();
        P[k]++;

        if(P[k] == N)
        {
            fout << "Ciclu negativ!";
            return 1;
        }

        for(int i = 0; i < V[k].size(); i++)
        {
            if(D[V[k][i].j] > D[k] + V[k][i].c)
            {
                D[V[k][i].j] = D[k] + V[k][i].c;
                Q.pb(V[k][i].j);
            }
        }
    }
    return 0;
}

void afis()
{
    for(int i = 2; i <= N; i++)
        fout << D[i] << " ";
}

int main()
{
    citire();
    if(BellmanFord(1) == 0)
        afis();

    fin.close();
    fout.close();
    return 0;
}