// 堆优化的dijkstra算法
// 通过使用优先对列优化了朴素dijkstra算法中找离当前源点最近的点
// q.push_back({w,v}),w为v到源点的距离
// 将权值放在第一位是因为pair中会优先对第一个元素排序

// 1.邻接表存储
/*#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;

using ll = long long ;
const int N = 1e5 + 50;
int n,m,s;
struct edge {int v,w;};
vector<edge> e[N];
int d[N];
bool vis[N];
priority_queue<pair<int,int> > q;

void dijkstra(int s) {
	for (int i = 1;i <= n; i++) d[i] = inf;
	d[s] = 0;
    q.push({0,s});
    while (q.size()) {
    	auto t = q.top(); q.pop();
    	int u = t.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (auto c:e[u]) {
        	int v = c.v; int w = c.w;
            if (d[v] > d[u] + w) {
            	d[v] = d[u] + w; // 松弛操作
            	q.push({-d[v],v});
            }
        }
    }
} 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1;i <= m; i++) {
    	int u,v,w; cin >> u >> v >> w;
    	e[u].push_back({v,w});
    }
    dijkstra(s);
    for (int i = 1;i <= n; i++) cout << d[i] << " ";
	return 0;
}*/

// 2.链式前向星存储
#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;

using ll = long long ;
const int N = 1e5 + 50 ;
int n,m,s;
struct edge {
	int to,ne,w;
}edge[N];
int head[N],cnt;
void add(int u,int v,int w) {
	cnt++;
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].ne = head[u];
    head[u] = cnt;
}
int d[N];
bool vis[N];
priority_queue<pair<int,int> > q;
void dijkstra(int s) {
	for (int i = 1;i <= n; i++) d[i] = inf;
	d[s] = 0;
    q.push({0,s});
    while (q.size()) {
    	auto t = q.top();q.pop();
    	int u = t.second;
    	if (vis[u]) continue;
    	vis[u] = true;
    	for (int i = head[u];i>0;i = edge[i].ne) {
    		int v = edge[i].to;
    		int w = edge[i].w;
    		if (d[v] > d[u] + w) {
    			d[v] = d[u] + w;
    			q.push({-d[v],v}); // 权值是-d[v],不是w也不是d[v]
    		}
    	} 
    } 
}
// 以上为链式前向星模版
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1;i <= m; i++) {
    	int u,v,w; cin >> u >> v >> w;
    	add(u,v,w);
    }
    dijkstra(s);
    for (int i = 1;i <= n; i++) cout << d[i] << " ";
	return 0;
}

上面注释掉的是我用vector模拟邻接表存储的,已经AC了,然后想着用链式前向星写一下,结果RE了四个点