//改进vector版Dijkstra
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
typedef pair<int, int> p;
//这里最好使用typedef 定义一下下面再用，如果直接vector<pair<int,int>> edges[10002];在OJ编程通不过…………
//priority_queue<pair<int, int> > qq;
// 注意在两个尖括号之间一定要留 空格，防止误判
vector<p> edges[10002];
long long dist[10002];
int visited[10002];
#define inf 0x3f3f3f3f
int n, m, s;
void Dijkstra()
{
fill(dist, dist + n+1, inf);
dist[s] =0;
for (int i=1; i <=n; i++)
{
int u=-1;
long long min= inf;
for (int j=1; j <=n; j++)
{
if (!visited[j] && dist[j] < min)
{
u =j; min= dist[j];
}
}
if (u==-1)return;
visited[u] =1;
for (int j=0; j <edges[u].size(); j++)//在以u为起点的所有边中寻找
{
int vv=edges[u][j].first;//是这条边的终点
if (!visited[vv])
{
if (min + edges[u][j].second< dist[vv])
dist[vv] =min + edges[u][j].second;
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin >> n >> m >> s;
for (int i=1; i <=m; i++)
{
int a, b, c;
cin >> a >> b >> c;
edges[a].push_back(make_pair(b, c));//使用每条边的起始节点作为edges的index，pair里是终点与权值
}
Dijkstra();
bool space=false;
for (int i=1; i <=n; i++)
{
if (visited[i])
printf("%s%d",space==false?"":" ", dist[i]);
else printf("%s%s", space==false ? "" : " ", "2147483647");
space =true;
}
}
//测试实例
//5 15 5
//2 2 270
//1 4 89
//2 1 3
//5 5 261
//5 2 163
//5 5 275
//4 5 108
//4 4 231
//3 4 213
//3 3 119
//3 1 77
//3 1 6
//2 4 83
//5 5 196
//5 5 94
//166 163 2147483647 246 0
