#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
using namespace std;

const int kNmax = 50005;
const int inf = 10000001;
class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	int source;
	vector<pair<int, int> > adj[kNmax];

	void read_input() {
		ifstream fin("bellmanford.in");
		fin >> n >> m >> source;
		for (int i = 1, x, y, w; i <= m; i++) {
			fin >> x >> y >> w;
			adj[x].push_back(make_pair(y, w));
		}
		fin.close();
	}

	vector<int> get_result() {
		
		vector<int> d(n + 1, 0);
		vector<int> cnt(n + 1, 0);
		set < pair<int,int> >Q;
		set < pair<int,int> >::iterator it;
		
		for (int i = 1; i <= n; i++) {
		    d[i] = inf;
		    cnt[i] = 0;
		}
		d[source] = 0;
		
		int no, dist;
		
		Q.insert(make_pair(0, source));
		while (!Q.empty()) {
		    it = Q.begin();
		    no = it->second;
		    dist = it->first;
		    Q.erase(it);
		    for (int i = 0; i < adj[no].size(); i++) {
		        int aux = d[adj[no][i].first];
		        if (aux > dist + adj[no][i].second) {
		            d[adj[no][i].first] = dist + adj[no][i].second;
		            Q.erase(make_pair(aux, adj[no][i].first));
		            Q.insert(make_pair(d[adj[no][i].first], adj[no][i].first));
		            cnt[adj[no][i].first]++;
		            if (cnt[adj[no][i].first] >= n) {
		                return vector<int>();
		            }
		        }
		    }
		}
		
		for (int i = 1; i <= n; i++)
		    if (d[i] == inf)
		        d[i] = -1;
		
		return d;
	}

	void print_output(vector<int> result) {
		ofstream fout("bellmanford.out");
		if (result.size() == 0) {
			fout << "Ciclu negativ!\n";
		} else {
			for (int i = 1; i <= n; i++) {
				fout << result[i] << ' ';
			}
			fout << '\n';
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}