# include <stdio.h>
# include <stdlib.h>
# include <limits.h>
# include <iostream>

using namespace std;

int n,m,s;
int ans[100005];
int heap[100005*4];
int vis[100005];
int len;

struct Head
{
	struct Node* next;
};

struct Node
{
	int point;
	int cost;
	struct Node* next;
};

void add(int x)
{
    heap[++len] = x;
    int now = len;

    while (now > 1)
    {
        int fa = now/2;
        if (ans[heap[fa]] > ans[heap[now]])
        {
            swap(heap[fa],heap[now]);
        }
        now = fa;
    }

    return ;
}

void del()
{
    heap[1] = heap[len--];
    int now = 1;

    while (now*2 <= len)
    {
        int son = now*2;
        if (son+1<=len && ans[heap[son+1]] < ans[heap[son]])
        {
            son++;
        }
        if (ans[heap[son]] < ans[heap[now]])
        {
            swap(heap[son],heap[now]);
        }
        now = son;
    }

    return ;
}

int main (void)
{
	scanf ("%d %d %d",&n,&m,&s);
	struct Head h[n+1];

	for (int i=0;i<=n;i++)
	{
		h[i].next = NULL;
		ans[i] = INT_MAX;
	}

	for (int i=0;i<m;i++)
	{
		int a,b,c;
		scanf ("%d %d %d",&a,&b,&c);
		struct Node* node = (struct Node*) malloc (sizeof(struct Node));
		node->next = h[a].next;
		node->cost = c;
		node->point = b;
		h[a].next = node;
	}


	ans[1] = 0;
	add(1);

	while (len>0)
	{
		int x = heap[1];
        del();
		if (vis[x])
        {
            continue;
        }
        vis[x] = 1;

		struct Node* temp = h[x].next;
		while (temp != NULL)
		{
			if (ans[x] + temp->cost < ans[temp->point])
			{
			    ans[temp->point] = ans[x] + temp->cost;
			    if (!vis[temp->point])
                {
                    add(temp->point);
                }
			}
			temp = temp->next;
		}
	}

	for (int i=1;i<=n;i++)
	{
		printf ("%d ",ans[i]);
	}
	return 0;
}