1 #include 
     
        2 #define For(i,j,k) for(int i=j;i<=k;i++) 3 #define Dow(i,j,k) for(int i=j;i>=k;i--) 4 #define LL long long 5 using namespace std ; 6 inline int read() { 7     int x = 0, f = 1; 8     char ch = getchar(); 9     while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); }10     while(ch>='0'&&ch<='9') { x = x * 10+ch-48; ch = getchar(); }11     return x * f;12 }13 inline void write(LL x) {14     if( x < 0 ) putchar('-');15     if( x > 9 ) write(x/10);16     putchar(x%10+48);17 }18 const int N = 10011, M = 500011; 19 const LL INF = 1e16; 20 int n, m, S, nedge; 21 int head[N], vis[N];22 LL dist[N];   23 struct edge{24     int to, pre, val; 25 }e[M];26 struct node{27     int id; 28     LL val; 29     friend bool operator <(node a, node b) {30         return a.val > b.val; 31     }32 };33 priority_queue
      
        Q; 34 inline void add(int x, int y, int v) {35     e[++nedge] = (edge){y, head[x], v};36     head[x] = nedge; 37 }38 void Dijkstra(int S) {39     For(i, 0, n) dist[i] = INF; 40     For(i, 0, n) vis[i] = 0; 41     dist[S] = 0; 42     while(!Q.empty()) Q.pop(); 43     44     Q.push((node){S, 0}); 45     while(!Q.empty()) {46         node p = Q.top(); Q.pop(); 47         int u = p.id; 48         if(vis[u]) continue; 49         vis[u] = 1; 50         for(int i=head[u]; i; i=e[i].pre) {       51             int v = e[i].to; 52             if(dist[u]+e[i].val < dist[v]) {53                 dist[v] = dist[u]+e[i].val; 54                 Q.push((node){v, dist[v]}); 55             }56         }57     }58 } 59 60 int main() {61     n = read(); m = read(); S = read(); 62     For(i, 1, m) {63         int x=read(), y=read(), v=read();64         add(x, y, v); 65     } 66     Dijkstra(S);67     For(i, 1, n) 68         if(dist[i] != INF) write(dist[i]), putchar(' '); 69         else printf("2147483647 "); 70     return 0; 71 }