import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
class Main
{
    static int N=500010;
    static int[] h=new int[N],e=new int[N],w=new int[N],ne=new int[N],dist=new int[N];
    static int INF=2147483647;
    static boolean[] st=new boolean[N];
    static int n,m,s,idx;
    public static void add(int a,int b,int c)
    {
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static void dijkstra(int s)
    {
        Arrays.fill(dist,INF);
        dist[s]=0;
        for(int i=0;i<n;i++)
        {
            int t=-1;
            for(int j=1;j<=n;j++)
            {
                if(!st[j]&&(t==-1||dist[t]>dist[j]))
                {
                    t=j;
                }
            }
            st[t]=true;
            for(int k=h[t];k!=-1;k=ne[k])
            {
                int m=e[k];
                dist[m]=Math.min(dist[m],dist[t]+w[k]);
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        Arrays.fill(h,-1);
        String[] str=reader.readLine().split(" ");
        n=Integer.parseInt(str[0]);
        m=Integer.parseInt(str[1]);
        s=Integer.parseInt(str[2]);
        while(m-->0)
        {
            String[] str1=reader.readLine().split(" ");
            int a=Integer.parseInt(str1[0]);
            int b=Integer.parseInt(str1[1]);
            int c=Integer.parseInt(str1[2]);
            add(a,b,c);
        }
        dijkstra(s);
        for(int i=1;i<=n;i++)
        {
            System.out.print(dist[i]+" ");
        }
    }
}