include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int maxn = 1e5 +5, maxm = 5e5 +5;
const int Inf = 0x3f3f3f3f;
struct Node{
int num, diss;
Node(){}
Node(int a,int b){
num = a;
diss = b;
}
bool operator <(const Node &a)const{
return diss > a.diss;
}
};
struct Edge{
int to, datd, next;
}e[maxm];
int n, m, s, len;
int haed[maxn];
void Ienst(int u, int v,int w){
e[len].to = v;
e[len].datd = w;
e[len].next = haed[u];
haed[u] = len;
}
void Read(){
scanf(“%d%d%d”, &n, &m, &s);
for(int i = 1; i <= m; i){
int u, v, w;
scanf(“%d%d%d”, &u, &v, &w);
if(u == v)continue;
Ienst(u, v, w);
}
}
bool f[maxn] = {};
int dis[maxn];
void djsl(int s){
memset(dis, 0x7f, sizeof(dis));
dis[s] = 0;
priority_queue[HTML_REMOVED] q;
q.push(Node(s, 0));
while(!q.empty()){
Node t = q.top();q.pop();
int u = t.num;
if(f[u] == 1)continue;
f[u] = 1;
for(int i = haed[u]; i; i = e[i].next){
int v = e[i].to, d;
if(dis[v] > (d = dis[u] + e[i].datd)&&f[v] == 0){
dis[v] = d;
q.push(Node(v, dis[v]));
}
}
}
}
int main(){
Read();
djsl(s);
for(int i = 1; i <= n; i++)
printf(“%d “, dis[i]);
return 0;
}