#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct Edge{
    int y;
    int weight;
};
struct Node{
    int vertex;
    int distance;
};
vector<Edge> graph[N]; //邻接表
int dist[N];
bool isVisit[N];
bool operator <(Node lhs,Node rhs){
    return lhs.distance>rhs.distance;
}
void Dijkstra(int s,int t,int n) {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INT_MAX;
        isVisit[i] = false;
    }
    dist[s] = 0;
    priority_queue<Node> pQueue;
    Node node;
    node.vertex = s;
    node.distance = dist[s];
    pQueue.push(node);
    while (!pQueue.empty()) {
        int vertex = pQueue.top().vertex;
        pQueue.pop();
        isVisit[vertex] = true;
        for (int i = 0; i < graph[vertex].size(); ++i) {
            Edge edge = graph[vertex][i];
            int y = edge.y;
            int weight = edge.weight;
            if (!isVisit[edge.y] && dist[vertex] + weight < dist[y]) {
                dist[y] = dist[vertex] + weight;
                node.vertex = y;
                node.distance = dist[y];
                pQueue.push(node);
            }
        }
    }
    printf("%d ", dist[t]);
}
int main(){
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for (int i = 1; i <= m; ++i) {
        Edge edge;
        int x;
        scanf("%d%d%d",&x,&edge.y,&edge.weight);
        graph[x].push_back(edge);
    }
    for (int i = 1; i <= n; ++i) {
        Dijkstra(s,i,n);
    }
    return 0;
}