#include<bits/stdc++.h>
#define int long long
#define M 500050
#define N 1050
#define inf (1ll<<31)-1
using namespace std;
int inq[N],dis[N];
queue<int>q;
struct node{
    int to,w;
};
vector<node>g[N];
int n,m,s;
void spfa() {
    for (int i = 1; i <= n; i++) {
        dis[i] = inf;
    }
    dis[s]=0;
    q.push(s);
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        for (int i=0;i<g[u].size();i++) {
            int v=g[u][i].to;
            int w=g[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v]=dis[u]+w;
                if (inq[v]==0) {
                    inq[v]=1;
                    q.push(v);

                }
            }
        }
        inq[u]=0;
    }
}

signed main(){
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
    }
    spfa();
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<" ";
    }
    return 0;
}

2，9，10RE