SPFA

#include<bits/stdc++.h>
using namespace std;
int n,dis[10005],v[10005];
struct node
{
	int w,len;
};
queue<int> r;
vector<node> e[10005];
void spfa(int s)
{
	for(int i=1;i<=n;i++){
		dis[i]=2147483647;
		v[i]=0;
	}
	v[s]=1;
	dis[s]=0;
	r.push(s);
	while(!r.empty()){
		int x=r.front();
		r.pop();
		v[x]=1;
		for(int i=0;i<e[x].size();i++){
			if(dis[e[x][i].w]>dis[x]+e[x][i].len){
				dis[e[x][i].w]=dis[x]+e[x][i].len;
				if(v[e[x][i].w]) continue;
				r.push(e[x][i].w);
			}
		}
	}
	return;
}
int main()
{
	int m,s;
	cin>>n>>m>>s;
	while(m--){
		int x,y,l;
		cin>>x>>y>>l;
		node h;
		h.w=y;
		h.len=l;
		e[x].push_back(h);
	}
	spfa(s);
	for(int i=1;i<=n;i++)
	cout<<dis[i]<<" ";
    return 0;
}