Dijkstra

#include<bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII;
const int N=5e5+10;
const int M=1e3+10;
int mod=1e9+7;
int dist[N];
vector<PII> adj[N];
int vis[N];
void dij(int sx){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,sx});
    dist[sx]=0;
    while(!q.empty()){
        int u=q.top().y;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto e:adj[u]){
            int v=e.x;
            int w=e.y;
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                q.push({dist[v],v});
            }
        }
    }
}

void solve(){
    int n,m,st;
    cin>>n>>m>>st;
    for(int i=1;i<=n;i++) dist[i]=1e18;
    for(int i=1;i<=m;i++){
        int u,v;
        int w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
    }   
    dij(st);
    for(int i=1;i<=n;i++){
        if(!vis[i]) cout<<-1<<" ";
        else cout<<dist[i]<<" ";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    _=1;
    //cin>>_;
    while(_--){
        solve();
    }
}