#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

priority_queue<pair<int, int>> myheap;
vector <int> vector_muchii[100001];
vector <int> vector_costuri[100001];
int viz[100001], dist[100001];
ifstream fin("dijkstra2.in");
ofstream fout("dijkstra2.out");
int n, m, p;

#define max_size 20000005
void citire()
{
    int i, j;
    fin >> n >> m >> p;
    for(i = 1; i <= m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        vector_muchii[x].push_back(y);
        vector_costuri[x].push_back(cost);

    }
}

void dijkstra()
{
    int i, vecin, lim, k;
    for(i = 1; i <= n; i++)
    {
        if(i == p)
            dist[i] = 0;
        else
            dist[i] = max_size;
        myheap.push(make_pair(-dist[i], i));
    }

    while(!myheap.empty())
    {
        pair<int, int> pr = myheap.top();

        int index = pr.second;
        myheap.pop();
        if(viz[index] == 1);

        else
        {
            viz[index] = 1;
            lim = vector_muchii[index].size();
            for(k = 0; k < lim; k++)
            {
                vecin = vector_muchii[index][k];
                if(dist[vecin] > (dist[index] + vector_costuri[index][k]))
                {
                    dist[vecin] = dist[index] + vector_costuri[index][k];
                    myheap.push(make_pair(-dist[vecin], vecin));
                    cout << "intra aici";
                }
            }
        }

    }
    for(i = 1; i <= n; i++)
    {
        if(dist[i] == max_size)
           dist[i] = 0;
        fout << dist[i] << " ";
    }
}
int main()
{

    citire();
    dijkstra();

    fin.close();
    fout.close();
    return 0;
}