#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct edge {
	int to, weight;
	edge(int to, int weight) : to(to), weight(weight) {}
};
int n, m;
vector<vector<edge> > graph(n, vector<edge>());
vector<int> Dist(n,0);
vector<int> Prev(n,0);

void dijkstra(int source) {
	int n = graph.size();
	vector<bool> s(n, false);
	fill(Dist.begin(), Dist.end(), INT_MAX);
	fill(Prev.begin(), Prev.end(), -1);
	Dist[source] = 0;
	for (int i = 1; i <= n; i++) {
		int u = -1;
		for(int j = 1; j <= n; j++){
			if(!s[j] && (u == -1 || Dist[j] < Dist[u])){
				u = j;
			}
		}
		s[u] = 1;
		for(edge e:graph[u]){
			if(!s[u] && Dist[e.to] > Dist[u] + e.weight){
				Dist[e.to] = Dist[u] + e.weight;
				Prev[e.to] = u;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int source;
	cin >> source;
	for(int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back(edge(v, w));
	}
	dijkstra(source);
	for(int i = 1; i <= n; i++){
		cout << Dist[i];
	}
	return 0;
}