include<bits/stdc++.h>

using namespace std; const int N=1e3+5; long long n,m,s; long long inf=0x7fffffff,minn=0; long long p,q,t; long long g[N][N]; long long dis[N],books[N]; int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) g[i][j]=0; else g[i][j]=inf; } } for(int i=1;i<=m;i++)
{ scanf("%d%d%d",&p,&q,&t); g[p][q]=min(t,g[p][q]); } books[s]=1; for(int i=1;i<=n;i++) { dis[i]=g[s][i]; } int u; for(int i=1;i<=n-1;i++) { minn=inf; for(int j=1;j<=n;j++) { if(books[j]==0&&dis[j]<minn) { minn=dis[j]; u=j; } } books[u]=1; for(int v=1;v<=n;v++) { if(g[u][v]<inf) { if(dis[v]>dis[u]+g[u][v]) { dis[v]=dis[u]+g[u][v]; } } } } for(int i=1;i<=n;i++) { cout<<dis[i]<<" "; } return 0; }

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
long long n,m,s;
long long inf=0x7fffffff,minn=0;
long long p,q,t;
long long g[N][N];
long long dis[N],books[N];
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) g[i][j]=0;
            else g[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++)   
    {
        scanf("%d%d%d",&p,&q,&t);
        g[p][q]=min(t,g[p][q]);
    }
    books[s]=1;
    for(int i=1;i<=n;i++)
    {
        dis[i]=g[s][i];
    }
    int u;
    for(int i=1;i<=n-1;i++)
    {
        minn=inf;
        for(int j=1;j<=n;j++)
        {
            if(books[j]==0&&dis[j]<minn)
            {
                minn=dis[j];
                u=j;
            }
        }
        books[u]=1;
        for(int v=1;v<=n;v++)
        {
            if(g[u][v]<inf)
            {
                if(dis[v]>dis[u]+g[u][v])
                {
                    dis[v]=dis[u]+g[u][v];
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }
    return 0;
}