#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

#define pi pair<int,int>

vector<pi >gr[10000];
int n,m,start,dist[10000];
bool used[10000];

void init(){
    int from,to,weight;

    scanf("%d %d %d",&n,&m,&start);

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&from,&to,&weight);

        gr[from].push_back({to,weight});
        ///gr[to].push_back({from,weight});
    }
}

void dijkstra(){
    int node;
    pi edge;
    priority_queue<pi,vector<pi >,greater<pi > >toVisit;///pairs, first is the distance, second is the node. By default pairs are compared by first element
    ///if the first elements are equal, then the second.
    fill(dist,dist+n,INT_MAX);///setting all distances to inf

    toVisit.push({0,start});///adding starting node
    dist[start]=0;///distance to first node is 0

    while(!toVisit.empty()){///while there are still unvisited nodes
        node=toVisit.top().second;///we need only the node, the distance is available in the distance array
        toVisit.pop();

        if(used[node])continue;///this is not the first time we meet the node, nothing to do

        used[node]=1;

        for(int ind=0;ind<gr[node].size();ind++){///for each neighbor of this node
            edge = gr[node][ind];///pair, first is the next node, second is the weight of the edge
            if(dist[node]+edge.second < dist[edge.first]){///if the new path is better
                dist[edge.first]=dist[node]+edge.second;
                toVisit.push({dist[edge.first],edge.first});///after we change the distance we must push in the queue again with the new value
            }
        }

    }
}

void print(){
    for(int ind=0;ind<n;ind++){
        printf("path to %d=%d\n",ind,dist[ind]);
    }
}

int main(){
    init();
    dijkstra();
    print();
}
/**
6 8 0
0 2 3
0 4 7
0 5 2
1 4 3
1 5 4
2 3 5
2 4 6
4 5 8
*/