#include <iostream>
#include <queue>
#include <list>

#define MAX_NODES 500
#define INF 99999

using namespace std;

struct Node
{
    int cost, at;
    Node(int a, int b): cost(a),at(b) {}
    Node(){}

};

struct adj
{
    list<Node> rel;
};

adj grafo[MAX_NODES];
int dist[MAX_NODES],
    N;

bool visited[MAX_NODES];

priority_queue<Node> pqueue;

bool operator<(const Node &leftNode, const Node &rightNode) {
 if (leftNode.cost != rightNode.cost) return leftNode.cost > rightNode.cost;
 if (leftNode.at != rightNode.at) return leftNode.at > rightNode.at;
 return false;
}


void dijkstra()
{
    for( int i = 0; i < MAX_NODES ; i++)
    {
            dist[i] = INF;
            visited[i] = false;
    }

    Node tmp, tmp2;

    while(pqueue.size())
    {
        tmp = pqueue.top();
        pqueue.pop();
        if (visited[tmp.at]) continue;

        visited[tmp.at] = true;

        while(!grafo[tmp.at].rel.empty()) //relações implementadas com listas ligadas
        {
            tmp2 = grafo[tmp.at].rel.front();
            grafo[tmp.at].rel.pop_front();

            if (dist[tmp2.at] > tmp.cost + tmp2.cost)
                {
                    dist[tmp2.at] = tmp.cost + tmp2.cost;
                    if(!visited[tmp2.at]) pqueue.push(Node(dist[tmp2.at],tmp2.at));
                }

        }

    }

}

int main()
{
    //input
    int source,dest, weight, goal;

    cin >> N >> goal;

    for( int i = 0; i < N ; i++ )
    {
        cin >> source >> dest >> weight;
        grafo[source].rel.push_back (Node(weight,dest));
    }

    pqueue.push(Node(0,goal));
    dijkstra();

    for(int i = 1; i<=N;i++)
        cout << i << " : " << dist[i] << endl;

    return 0;
}