WA

#include <bits/stdc++.h>
#include <queue>
#include <math.h>
using namespace std;

struct EDGE
{
    int to;
    int next;
    int value;
};

struct NODE
{
    int pos, dis;
    
    bool operator< (const NODE x)const {
        return x.dis < dis;
    }
};

EDGE edge[200000];
int head[100000], cnt = 0, dist[100000], s;
bool vis[100000];
priority_queue <NODE> q;

void dijkstra ()
{
    NODE tmp;
    int p;
    
    q.push(NODE{s, 0});
    
    while (!q.empty()) {
        tmp = q.top();
        q.pop();
        p = tmp.pos;
        
        if (vis[p]) {
            continue;
        }
        vis[p] = 1;
        
        int y;
        for (int i = head[p]; i != 0; i = edge[i].next) {
            y = edge[i].to;
            if (dist[y] > dist[p] + edge[i].value) {
                dist[y] = dist[p] + edge[i].value;
            }
            if (!vis[y]) {
                q.push(NODE{y, dist[y]});
            }
        }
        
    }
}

int main ()
{
    int n, m, u, v, w;
    
    cin >> n >> m >> s;
    
    memset(dist, INFINITY, 100000);
    memset(vis, false, 100000);
    
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        
        cnt++;
        edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt;
        edge[cnt].value = w;
    }
    
    dist[s] = 0;
    
    dijkstra();
    
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
    
    return 0;
}