# include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, M = 1e6 + 5, LIM = 3e6 + 5; 
struct DSU
{
	int f[N];
	void Init(int n)
	{
		for(int i = 1; i <= n; i++) f[i] = i; return; 
	}
	int find(int x)
	{
		if(x != f[x]) f[x] = find(f[x]); return f[x]; 
	}
	void merge(int x, int y)
	{
		x = find(x), y = find(y); if(x == y) return; f[y] = x; return; 
	}
}dsu; 
struct Opt
{
	int u1, v1, u2, v2, w; 
}; vector <Opt> Opts; 
struct edge
{
	int v, w; 
};
vector <edge> G[LIM];
void adde(int u, int v, int w = 0) {G[u].push_back({v, w}); }
int n, m, S; 
int fa[16][N], Down[16][N], Up[16][N], btot, dep[N]; 
void dfs(int x, int fa)
{
	::fa[0][x] = fa; dep[x] = dep[fa] + 1; 
	for(int i = 1; i <= 15; i++) ::fa[i][x] = ::fa[i - 1][::fa[i - 1][x]];
	for(auto I : G[x])
	{
		int v = I.v;
		if(v == fa) continue;  
		dfs(v, x);
	}
	return; 
}
void build(void)
{
	for(int i = 1; i <= n; i++) Down[0][i] = i, Up[0][i] = i + n, adde(i, i + n), adde(i + n, i);
	for(int j = 1; j <= 15; j++)
		for(int i = 1; i <= n; i++) Down[j][i] = ++btot, Up[j][i] = ++btot; 
	for(int j = 1; j <= 15; j++)
	{
		for(int i = 1; i <= n; i++) 
		{
			adde(Down[j][i], Down[j - 1][i]), adde(Down[j][i], Down[j - 1][fa[j - 1][i]]);
			adde(Up[j - 1][i], Up[j][i]), adde(Up[j - 1][fa[j - 1][i]], Up[j][i]);
		}
	}
	return; 
}
void Modi(int u, int v, int idx, int w, bool opt) // opt = 0 Up[u, v] -> idx; opt = 1 idx -> Down[u, v]
{
	if(dep[u] > dep[v]) swap(u, v); 
	for(int i = 15; i >= 0; i--) 
	{
		if(dep[u] + (1 << i) <= dep[v])
		{
			if(!opt) adde(Up[i][v], idx, w); 
			else adde(idx, Down[i][v], w); 
			v = fa[i][v]; 
		}
	}
	if(u == v)
	{
		if(!opt) adde(Up[0][u], idx, w);
		else adde(idx, Down[0][u], w); 
		return; 
	}
	for(int i = 15; i >= 0; i--)
	{
		if(fa[i][u] != fa[i][v])
		{
			if(!opt) adde(Up[i][u], idx, w), adde(Up[i][v], idx, w); 
			else adde(idx, Down[i][u], w), adde(idx, Down[i][v], w); 
			u = fa[i][u], v = fa[i][v]; 
 		}
	}
	if(!opt) adde(Up[1][u], idx, w), adde(Up[1][v], idx, w); 
	else adde(idx, Down[1][u], w), adde(idx, Down[1][v], w); 
	return; 
}
int dis[LIM]; bitset <LIM> vis; 
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q; 
void dij(void)
{
	for(int i = 0; i <= btot; i++) dis[i] = 1e9; 
	dis[S] = 0; Q.push({0, S}); 
	while(!Q.empty())
	{
		int x = Q.top().second; Q.pop();
		if(vis[x]) continue; vis[x] = 1; 
		for(auto I : G[x])
		{
			int v = I.v, w = I.w; 
			if(dis[v] > dis[x] + w) 
			{
				dis[v] = dis[x] + w; Q.push({dis[v], v});
			}
		}
	}
	return; 
}
int main(void)
{
	scanf("%d%d%d", &n, &m, &S); btot = n * 2; 
	dsu.Init(n); 
	for(int i = 1; i <= m; i++)
	{
		int opt; scanf("%d", &opt); 
		if(opt == 1)
		{
			int u1, v1, u2, v2, w; scanf("%d%d%d%d%d", &u1, &v1, &u2, &v2, &w); 
			if(dsu.find(u1) != dsu.find(v1) || dsu.find(u2) != dsu.find(v2)) continue; 
			Opts.push_back({u1, v1, u2, v2, w});
		}
		else
		{
			int u, v, w; scanf("%d%d%d", &u, &v, &w);
			adde(u, v, w); adde(v, u, w); 
			dsu.merge(u, v);
		}
	}
	for(int i = 1; i <= n; i++) if(!fa[0][i]) dfs(i, 0);
	build(); 
	for(auto I : Opts)
	{
		++btot; 
		Modi(I.u1, I.v1, btot, I.w, 0); 
		Modi(I.u2, I.v2, btot, 0, 1); 
	}
	dij(); 
	for(int i = 1; i <= n; i++) printf("%d%c", dis[i] >= 1e9 ? -1 : dis[i], " \n"[i == n]); 
	return 0; 
}