#include<stdio.h>
#define N_MAX 1024*50
#define INFINIT 0x7FFFFFFF

struct entry
{
	int val, cost;
	entry * next;
} *start[N_MAX], *stop[N_MAX], *p;

int n, m, cost[N_MAX], best[N_MAX];

void add(int a, int b, int cost)
{
	p=new entry;
	p->next=NULL;
	p->val=b;
	p->cost=cost;
	if (start[a]==NULL)
	{
		start[a]=p;
		stop[a]=p;
	}
	else
	{
		stop[a]->next=p;
		stop[a]=stop[a]->next;
		
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	int i, a, b, cst, min, k, nr=0, st;
	scanf("%d %d %d", &n, &m, &st);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d", &a, &b, &cst);
		add(a, b, cst);
	}
	
	for (i=1; i<=n; i++)
	{
		cost[i]=INFINIT;
		best[i]=INFINIT;
	}
	cost[st]=0;
	
	while (nr<n)
	{
		min=INFINIT;
		for (i=1; i<=n; i++)
			if (cost[i]<=min)
			{
				min=cost[i];
				k=i;
			}
		best[k]=cost[k];
		++nr;
		cost[k]=INFINIT;		
		p=start[k];
		while(p!=NULL)
		{
			if (( best[k]+p->cost < cost[p->val] ) && (best[p->val]==INFINIT))
				cost[p->val]=best[k]+p->cost;
			p=p->next;
		}
	
	}
	for (i=1; i<=n; i++)
	{
		//printf("de la nodul %d la nodul %d avem drum de cost minim %d\n", st, i, best[i]);
		printf("%d\n", best[i]);
	}
	fclose(stdout);
	return 0;
}