#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define NMAX 1000
#define INF 999999999
#define fori(i,a,b) for(int i=a; a<=b; i++)

using namespace std;

ifstream fin;
ofstream fout;

int n;              //nr of vertices
int startVertex;    //the starting vertex
int minCost[NMAX];  //the minimum cost to the starting vertex
bool inQueue[NMAX]; //if the given vertex is or isn't in the priority queue

struct Compare {
    bool operator()(int x, int y)
    {
        return minCost[x] > minCost[y];
    }
};


vector < pair <int, int> > Graph[NMAX];

priority_queue <int, vector<int>, Compare> priorityQueue;

void addEdge(int x, int y, int weight)
{
    /**
     * Inserts the edge into the graph
     * @param x = starting vertex
     * @param y = ending vertex
     * @param weight = the weight of the edge
     */
    Graph[x].push_back(make_pair (y, weight));
}

void read()
{
    fin >> n >> startVertex;

    int x, y, w;
    while(fin >> x >> y >> w) {
        addEdge(x, y, w);
    }
}

void Dijkstra(int startingVertex)
{
    /**
     * Calculates the minimum cost road between any vertex and the @param startingVertex
     */
    for(int i=1; i<=n; i++)
        minCost[i] = INF;

    minCost[startingVertex] = 0;

    priorityQueue.push(startingVertex);
    inQueue[startingVertex] = true;

    while (!priorityQueue.empty())
    {
        int currentVertex = priorityQueue.top();

        priorityQueue.pop();
        inQueue[currentVertex] = false;

        for(size_t i=0; i<Graph[currentVertex].size(); i++)
        {
            int neighbour = Graph[currentVertex][i].first;
            int weight = Graph[currentVertex][i].second;

            if (minCost[currentVertex] + weight < minCost[neighbour])
            {
                minCost[neighbour] = minCost[currentVertex] + weight;

                if (!inQueue[neighbour])
                {
                    priorityQueue.push(neighbour);
                    inQueue[neighbour] = true;
                }
            }
        }
    }

}

void write()
{
    for(int i=1; i<=n; i++)
    {
        if(minCost[i] != INF)
            fout << minCost[i] << " ";
        else
            fout << "-1 ";

    }
}

int main() {
    fout.open("dijkstra.out");
    fin.open("dijkstra.in");

    read();
    Dijkstra(startVertex);
    write();


    fin.close();
    fout.close();

    return 0;
}