我是分三个点集：第一颗线段树是维护点到区间上，1 ~ 4n，第二颗线段树是区间到点，1 + 4n ~ n + 4n，最后是原图中的点 1 + 8n ~ n + 8n

#include <bits/stdc++.h>
#define re register int 
#define lp p << 1
#define rp p << 1 | 1
#define n4 4 * n
#define n8 8 * n

using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 9e5 + 10, M = 2e6 + 10;
const LL inf = 1e18 + 10;

struct Edge
{
	int to, next;
	LL w;
}e[M];
int idx, h[N];
struct Tree
{
	int l, r;
}t[N];
int n, q, s;
LL dis[N];
bool st[N];

inline void add(int x, int y, LL w)
{
	++ idx;
	e[idx].to = y, e[idx].w = w, e[idx].next = h[x];
	h[x] = idx;
}

inline void build(int p, int l, int r)
{
	t[p].l = l, t[p].r = r;
	if (l == r)
	{
		add(p, l + n8, 0), add(l + n8, p, 0);
		add(p + n4, l + n8, 0), add(l + n8, p + n4, 0);
		return;
	}
	add(p, lp, 0), add(p, rp, 0);
	add(lp + n4, p + n4, 0), add(rp + n4, p + n4, 0);
	
	int mid = (l + r) >> 1;
	build(lp, l, mid); build(rp, mid + 1, r);
}

inline void update(int p, int l, int r, int u, LL w, int type)
{
	if (l <= t[p].l && t[p].r <= r)
	{
		if (type) add(p + n4, u + n8, w);
		else add(u + n8, p, w);
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) update(lp, l, r, u, w, type);
	if (r > mid) update(rp, l, r, u, w, type);
}

inline void dij()
{
	priority_queue<PII, vector<PII>, greater<PII> > q;
	for (re i = 1; i <= n + n8; i ++) dis[i] = inf;
	
	dis[s + n8] = 0;
	q.push({0, s + n8});
	while (!q.empty())
	{
		int x = q.top().second; q.pop();
		if (st[x]) continue;
		st[x] = true;
		
		for (re i = h[x]; i; i = e[i].next)
		{
			int y = e[i].to; LL w = e[i].w;
			if (dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				q.push({dis[y], y});
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> q >> s;
	build(1, 1, n);
	while (q --)
	{
		int op, u, v, l, r; LL w; 
		cin >> op;
		if (op == 1)
		{
			cin >> u >> v >> w;
			add(u + n8, v + n8, w);
		}
		if (op == 2) // u -> [l, r]
		{
			cin >> u >> l >> r >> w;
			update(1, l, r, u, w, 0);
		}
		if (op == 3) // [l, r] -> u
		{
			cin >> u >> l >> r >> w;
			update(1, l, r, u, w, 1);
		}
	}	
	dij();
	for (re i = 1; i <= n; i ++) cout << (dis[i + n8] == inf ? -1 : dis[i + n8]) << ' ';
	cout << '\n';
	
	return 0;
}