#include <bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
struct Node{ll va,id; bool operator<(const Node&a)const{return va>a.va;}};
vector<int> to[N],w[N];
ll n,m,s,d[N],ok[N];
void dijkstra(){
    fill(d,d+n+9,1e9);
    priority_queue<Node> q;
    d[s]=0; q.push((Node){0,s});
    while(!q.empty()){
        ll u=q.top().id; q.pop();
        if(ok[u]) continue;
        ok[u]=1;
        for(int i=0;i<to[u].size();i++){
            ll v=to[u][i];
            if(d[v]>d[u]+w[u][i]){
                d[v]=d[u]+w[u][i];
                if(!ok[v]) q.push((Node){d[v],v});
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1,u,v,va;i<=n;i++){
        cin>>u>>v>>va;
        to[u].push_back(v); w[u].push_back(va);
    }
    dijkstra();
    for(int i=1;i<=n;i++) cout<<d[i]<<" ";
    return 0;
}

只有5#过了嘤嘤嘤