#include <bits/stdc++.h>
using namespace std;
int n, m, s;
int x, y, w;
int f[105][105];
int main()
{
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
    cin >> n >> m >> s;
    for(int i = 1;i <= m; i++)
    {
        cin >> x >> y >> w;
        f[x][y] = f[y][x] = w;
    }
    for(int k = 1;k <= n; k++)
 	    for(int i = 1;i <= n; i++)
    		for(int j = 1;j <= n; j++)
        		f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	for(int i = 1;i <= n; i++)
		cout << f[s][i] << ' ';
	 
    return 0;
}