#include <algorithm>

using namespace std;

const int N = 1010, M = 2000010, INF = 1000000000;

int n, m;
int d[N][N];

int ()
{
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			d[i][j] = i == j ? 0 : INF;
		}
	}

	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		d[a][b] = d[b][a] = min(c, d[a][b]);
	}
	
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	cout << d[1][n] << endl;
	return 0;
}

#include <cstring>

#include <queue>
#include <algorithm>
using namespace std;

const int M = 200000 + 100;
const int N = 100000 + 100;
int hd[N], nxt[M], to[M], w[M];

int dist[N], vis[N];
int cnt;

inline void add(int x, int y, int z)
{
	to[++cnt] = y;
	w[cnt] = z;
	nxt[cnt] = hd[x];
	hd[x] = cnt;
}

struct Node
{
	int nd, val;
	bool operator < (const Node& b) const
	{
		return val > b.val;
	}
};

priority_queue<Node> q;

void xhl(int beg)
{
	memset(vis, 0, sizeof vis);
	memset(dist, 0x3f, sizeof dist);

	dist[beg] = 0;
	q.push({ beg,0 });

	while (q.size())
	{
		int x = q.top().nd;
		q.pop();

		if (vis[x])
		{
			continue;
		}
		vis[x] = true;

		for (int i = hd[x]; i; i = nxt[i])
		{
			int y = to[i], wi = w[i];
			if (dist[y] > dist[x] + wi)
			{
				dist[y] = dist[x] + wi;
				q.push({ y,dist[y] });
			}
		}
	}
}

int n, m, s;

int ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> s;

	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
	}
	xhl(s);
	for (int i = 1; i <= n; i++)
	{
		cout << dist[i] << " ";
	}
	cout << endl;
}