#include<fstream>
#include<vector>
#include<set>

using namespace std;

const int INF = 1000000000;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector< pair<int,int> > a[100];
set< pair<int,int> > q;
vector<int> d(100,INF), p(100);

int main(){
    int n,m,i,j,x,y,z,s,v,vl,to,ln;

    f>>n>>m>>s;
    for(i=1; i<=m; ++i){
        f>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }

    d[s]=0;

    q.insert(make_pair(d[s],s));

    while(!q.empty()){
        v=q.begin()->second;
        vl=q.begin()->first;
        q.erase(q.begin());

        for(i=0; i<a[v].size(); ++i){
            to=a[v][i].first;
            ln=a[v][i].second;
            if(vl+ln < d[to]){
                q.erase(make_pair(ln,to));
                d[to]=vl+ln;
                p[to]=v;
                q.insert(make_pair(d[to],to));
            }
        }
    }

    for(i=1; i<= n; ++i)
        g<<d[i]<<' ';


return 0;
}