巨弱一个（我的输入法没有ju·ruo），学dij和spfa后倒腾优化最后这样一个代码（下），既可以跑负边，还可以过dij的模版题，所以他是dij还是spfa

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000+10
int n,m;

struct node {
	int v,w;
};
bool operator < (const node& a,const node& b) {
	return a.w>b.w;
}
vector <node> g[maxn];
int f[maxn];
bool vis[maxn];
priority_queue<node> q;
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		f[i]=1<<30;
	}
	f[s]=0;
	q.push( (node){s,0} );
	
	while(q.size()!=0){
		node t=q.top();
		q.pop();
		if(vis[t.v]) continue;
		else vis[t.v]=1;
		
		for(int i=0;i<g[t.v].size();i++){
			node to=g[t.v][i];
			if(f[to.v]>f[t.v]+to.w){
				f[to.v]=f[t.v]+to.w;
				q.push((node){to.v,f[to.v]});
			}
		}
	}
}
int main(){
    int x;
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=m;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		g[x].push_back( (node){y,w} );
	}
	dijkstra(x);
    int maxx=0;
    for(int i=1;i<=n;i++){
        cout<<f[i]<<" ";
    }
	return 0;
}