using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace DoubleDijkstra
{
    class Program
    {
        static int Min(int[] length, int N, bool[] used)
        {
            int min = int.MaxValue;
            int v = -1;
            for (int i = 1; i <= N; ++i)
            {
                if (length[i] <= min)
                {

                    if (used[i] == false)
                    {
                        min = length[i];
                        v = i;
                    }
                }
            }
            return v;
        }


        static void Main(string[] args)
        {

            bool[] used;
            int[] length;
            int N;
            int S;
            int Edge;
            int[] SV;
            int[] EV;
            int[] weight;

            using (StreamReader sr = new StreamReader("input.txt"))
            {
                string[] str = sr.ReadLine().Split(' ');
                N = int.Parse(str[0]);
                Edge = int.Parse(str[1]);
                S = int.Parse(str[2]);
                weight = new int[Edge + 1];
                EV = new int[Edge + 1];
                SV = new int[Edge + 1];
                length = new int[N + 1];
                used = new bool[N + 1];
                for (int i = 1; i <= Edge; ++i)
                {
                    str = sr.ReadLine().Split(' ');
                    SV[i] = int.Parse(str[0]);
                    EV[i] = int.Parse(str[1]);
                    weight[i] = int.Parse(str[2]);
                }

            }

            for (int i = 1; i <= N; ++i)
            {
                if (i == S)
                {
                    length[i] = 0;
                }
                else
                {
                    length[i] = int.MaxValue;
                }
                used[i] = false;
            }
            //int c = 0;


            for (int j = 1; j <= N; ++j)
            {
                int c = Min(length, N, used);
                for (int i = 1; i <= Edge; ++i)

                {
                    if (SV[i] == c)
                    {
                        int maybe = length[SV[i]] + weight[i];
                        if (maybe >= 0)
                        {
                            if (maybe < length[EV[i]])
                            {
                                length[EV[i]] = maybe;
                            }


                        }

                    }
                }
                used[c] = true;
            }
            using (StreamWriter sr = new StreamWriter("output.txt"))
            {
                for (int i = 1; i <= N; ++i)
                {
                    if (length[i] == int.MaxValue)
                    {
                        length[i] = -1;
                    }
                    sr.Write(length[i]);
                    sr.Write(' ');
                }
            }




        }




    }
}

/*using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int N;
            int M;
            int[] SV;
            int[] EV;
            int[] weigth;
            int Edge;
            int[,] d;
            using (StreamReader sr = new StreamReader("input.txt"))
            {
                string[] str = sr.ReadLine().Split(' ');
                N = int.Parse(str[0]);
                Edge = int.Parse(str[1]);

                SV = new int[N+1];
                EV = new int[N + 1];
                weigth = new int[N + 1];
                d = new int[N+1,N+1];
                for (int i = 1; i <= Edge; ++i)
                {
                    str = sr.ReadLine().Split(' ');
                    SV[i] = int.Parse(str[0]);
                    EV[i] = int.Parse(str[1]);
                    weigth[i] = int.Parse(str[2]);
                }


            }
            for (int i = 1; i <= N; ++i)
            {
                for (int j = 1; j <= N; ++j)
                {
                    d[i, j] = int.MaxValue;
                    for (int s = 1; s <= Edge; ++s)
                    {
                        if (SV[s] == i)
                        {
                            d[SV[s], EV[s]] = weigth[s];
                        }
                    }
                }
            }
            for (int i = 1; i <= N; ++i)
            {
                for (int j = 1; j <= N; ++j)
                {
                    using (StreamWriter sr = new StreamWriter("output.txt"))
                    {
                        sr.Write(d[i,j]);
                        sr.Write(' ');
                    }
                }
            }
        }
    }
}
*/