友情提示： 该题须开long long，且对设置的INF有较大要求，须开到极大

#include<bits/stdc++.h>
#define MaxN 100010
#define MaxM 500010
#define ll long long
#define inf 114514191981019260817
using namespace std;
struct edge
{
    ll to, dis, next;
};
edge e[MaxM];
ll head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
ll n, m, s;
inline void add_edge( int u, int v, int d )
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
struct node
{
    ll dis;
    ll pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
priority_queue < node > q;
inline void dijkstra()
{
    dis[s] = 0;
    q.push( ( node ){0, s} );
    while( !q.empty() )
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] )
            continue;
        vis[x] = 1;
        for(ll i = head[x]; i; i = e[i].next)
        {
            ll y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis )
            {
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] )
                {
                    q.push( ( node ){dis[y], y} );
                }
            }
        }
    }
}
int main()
{
    scanf( "%lld%lld%lld", &n, &m, &s );
    for(int i = 1; i <= n; ++i) dis[i] = inf;
    for(ll i = 0; i < m; ++i )
    {
        ll u, v, d;
        scanf( "%lld%lld%lld", &u, &v, &d );
        add_edge( u, v, d );
    }
    dijkstra();
    for( int i = 1; i <= n; i++ )
        printf( "%lld ", dis[i] );
    return 0;
}