stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mod 1000000007

using namespace std;



int n;

long long dp1[300010],dp2[300010],a[300010],sum1,sum2;



priority_queue<long long,vector<long long>,greater<long long> > q;

priority_queue<long long> q2;



int main()

{

	//fuck!!!

	scanf("%d",&n);

	memset(dp1,0,sizeof(dp1));

	memset(dp2,0x3f,sizeof(dp2));

	for(int i=1;i<=3*n;i++)

	{

		scanf("%lld",&a[i]);

	}

	for(int i=1;i<=n;i++)

	{

		q.push(a[i]);

		sum1+=a[i];

	}

	dp1[n]=sum1;

	for(int i=n+1;i<=3*n;i++)

	{

		if(q.top()<a[i])

		{

			sum1-=q.top();

			sum1+=a[i];

			q.pop();

			q.push(a[i]);

		}

		dp1[i]=sum1;

	}

	for(int i=3*n;i>2*n;i--)

	{

		q2.push(a[i]);

		sum2+=a[i];

	}

	dp2[2*n+1]=sum2;

	for(int i=2*n;i>=1;i--)

	{

		if(q2.top()>a[i])

		{

			sum2-=q2.top();

			sum2+=a[i];

			q2.pop();

			q2.push(a[i]);

		}

		dp2[i]=sum2;

	}

	long long ans=-0x3f3f3f3f3f3f3f3f;

	for(int i=n;i<=2*n;i++)

	{

//		printf("%d %lld %lld\n",i,dp1[i],dp2[i]);

		ans=max(ans,dp1[i]-dp2[i+1]);

	}

	printf("%lld\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.858709891589836x):
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<set>

using namespace std;



const long long inf=1e18;

const int maxn=3e5+5;



multiset <int> s;

multiset <int,greater<int> > t;

long long a[maxn],b[maxn],c[maxn],n,now,ans;



int main()

{

	ans=-inf;

    cin>>n;

    for(long long i=1;i<=n*3;i++)

    {

        scanf("%lld",&a[i]);

        s.insert(a[i]);

        now=now+a[i];

        if(s.size()>n)

        {

            now-=*s.begin();

            s.erase(s.begin());

        }

        b[i]=now;

    }

    now=0;

    for(long long i=n*3;i>=1;i--)

    {

        t.insert(a[i]);

        now=now+a[i];

        if(t.size()>n)

        {

            now-=*t.begin();

            t.erase(t.begin());

        }

        c[i]=now;

    }

    for(long long i=n;i<=n*2;i++)

    {

        ans=max(ans,b[i]-c[i+1]);

    }

    cout<<ans;

    return 0;

}
// Slower C++ solution:
#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mod 1000000007

using namespace std;



int n;

long long dp1[300010],dp2[300010],a[300010],sum1,sum2;



priority_queue<long long,vector<long long>,greater<long long> > q;

priority_queue<long long> q2;



int main()

{

	//fuck!!!

	scanf("%d",&n);

	memset(dp1,0,sizeof(dp1));

	memset(dp2,0x3f,sizeof(dp2));

	for(int i=1;i<=3*n;i++)

	{

		scanf("%lld",&a[i]);

	}

	for(int i=1;i<=n;i++)

	{

		q.push(a[i]);

		sum1+=a[i];

	}

	dp1[n]=sum1;

	for(int i=n+1;i<=3*n;i++)

	{

		if(q.top()<a[i])

		{

			sum1-=q.top();

			sum1+=a[i];

			q.pop();

			q.push(a[i]);

		}

		dp1[i]=sum1;

	}

	for(int i=3*n;i>2*n;i--)

	{

		q2.push(a[i]);

		sum2+=a[i];

	}

	dp2[2*n+1]=sum2;

	for(int i=2*n;i>=1;i--)

	{

		if(q2.top()>a[i])

		{

			sum2-=q2.top();

			sum2+=a[i];

			q2.pop();

			q2.push(a[i]);

		}

		dp2[i]=sum2;

	}

	long long ans=-0x3f3f3f3f3f3f3f3f;

	for(int i=n;i<=2*n;i++)

	{

//		printf("%d %lld %lld\n",i,dp1[i],dp2[i]);

		ans=max(ans,dp1[i]-dp2[i+1]);

	}

	printf("%lld\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.891441645144762x):
#include<bits/stdc++.h>

#define LL long long

#define MEM(x,y) memset(x,y,sizeof(x))

#define MOD(x) ((x)%mod)

#define mod 1000000007

#define pb push_back

#define STREAM_FAST ios::sync_with_stdio(false)



using namespace std;

const int maxn = 3e5+7;



map<LL,int>vis;

int n;

struct Lpart

{

    int id;LL val;

    Lpart(int id,LL val):id(id),val(val){}

    Lpart(){}

    bool operator < (const Lpart &rhs) const

    {

        return val>rhs.val;

    }

};



struct Rpart

{

    int id;LL val;

    Rpart(int id,LL val):id(id),val(val){}

    Rpart(){}

    bool operator < (const Rpart &rhs) const

    {

        return val<rhs.val;

    }

};



priority_queue<Lpart>Lq;

priority_queue<Rpart>Rq;



LL a[maxn],lsum[maxn],rsum[maxn];



void getlsum()

{

    LL sum=0;

    for (int i=1;i<=3*n;i++)

    {

        Lq.push(Lpart(i,a[i]));

        if (Lq.size()==n+1)

        {

            sum-=Lq.top().val;Lq.pop();

        }

        sum+=a[i];lsum[i]=sum;

    }

}



void getrsum()

{

    LL sum=0;

    for (int i=3*n;i>=1;i--)

    {

        Rq.push(Rpart(i,a[i]));

        if (Rq.size()==n+1)

        {

            sum-=Rq.top().val;Rq.pop();

        }

        sum+=a[i];rsum[i]=sum;

    }

}



int main()

{

    scanf("%d",&n);

    for (int i=1;i<=3*n;i++) scanf("%lld",&a[i]);

    getlsum();

    getrsum();

    LL ans=-1e18;

    for (int i=n;i<=2*n;i++)

    {

        ans=max(ans,lsum[i]-rsum[i+1]);

    }

    printf("%lld\n",ans);

    return 0;

}
// Slower C++ solution:
#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mod 1000000007

using namespace std;



int n;

long long dp1[300010],dp2[300010],a[300010],sum1,sum2;



priority_queue<long long,vector<long long>,greater<long long> > q;

priority_queue<long long> q2;



int main()

{

	//fuck!!!

	scanf("%d",&n);

	memset(dp1,0,sizeof(dp1));

	memset(dp2,0x3f,sizeof(dp2));

	for(int i=1;i<=3*n;i++)

	{

		scanf("%lld",&a[i]);

	}

	for(int i=1;i<=n;i++)

	{

		q.push(a[i]);

		sum1+=a[i];

	}

	dp1[n]=sum1;

	for(int i=n+1;i<=3*n;i++)

	{

		if(q.top()<a[i])

		{

			sum1-=q.top();

			sum1+=a[i];

			q.pop();

			q.push(a[i]);

		}

		dp1[i]=sum1;

	}

	for(int i=3*n;i>2*n;i--)

	{

		q2.push(a[i]);

		sum2+=a[i];

	}

	dp2[2*n+1]=sum2;

	for(int i=2*n;i>=1;i--)

	{

		if(q2.top()>a[i])

		{

			sum2-=q2.top();

			sum2+=a[i];

			q2.pop();

			q2.push(a[i]);

		}

		dp2[i]=sum2;

	}

	long long ans=-0x3f3f3f3f3f3f3f3f;

	for(int i=n;i<=2*n;i++)

	{

//		printf("%d %lld %lld\n",i,dp1[i],dp2[i]);

		ans=max(ans,dp1[i]-dp2[i+1]);

	}

	printf("%lld\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.8947391817538355x):
#include<bits/stdc++.h>

using namespace std;



priority_queue<long long>x; 

priority_queue<long long ,vector<long long>,greater<long long> >y;

long long l[300001],r[300001],s[300001]; 

int main()

{

	int n,m,t;	

	long long ans=-100000000000000,p,q;	

	scanf("%d",&n);

	for(int i=1;i<=3*n;i++)

	{

	    scanf("%lld",&s[i]);

	}

	p=0;

	q=0;

	for(int i=1;i<=3*n;i++)

	{

		y.push(s[i]);

		p+=s[i];

		l[i]=p;

		x.push(s[3*n-i+1]);

		q+=s[3*n-i+1];

		r[3*n-i+1]=q;

		if(y.size()>n)

		{

			p-=y.top();

			l[i]=p;

			y.pop();

		}

		if(x.size()>n)

		{

			q-=x.top();

			r[3*n-i+1]=q;

			x.pop();

		}

	}

	for(int i=n;i<=2*n;i++)

	{

		if (l[i]-r[i+1]>ans) 

		  ans=l[i]-r[i + 1];

	}

	printf("%lld",ans);

	return 0;

}
// Slower C++ solution:
#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mod 1000000007

using namespace std;



int n;

long long dp1[300010],dp2[300010],a[300010],sum1,sum2;



priority_queue<long long,vector<long long>,greater<long long> > q;

priority_queue<long long> q2;



int main()

{

	//fuck!!!

	scanf("%d",&n);

	memset(dp1,0,sizeof(dp1));

	memset(dp2,0x3f,sizeof(dp2));

	for(int i=1;i<=3*n;i++)

	{

		scanf("%lld",&a[i]);

	}

	for(int i=1;i<=n;i++)

	{

		q.push(a[i]);

		sum1+=a[i];

	}

	dp1[n]=sum1;

	for(int i=n+1;i<=3*n;i++)

	{

		if(q.top()<a[i])

		{

			sum1-=q.top();

			sum1+=a[i];

			q.pop();

			q.push(a[i]);

		}

		dp1[i]=sum1;

	}

	for(int i=3*n;i>2*n;i--)

	{

		q2.push(a[i]);

		sum2+=a[i];

	}

	dp2[2*n+1]=sum2;

	for(int i=2*n;i>=1;i--)

	{

		if(q2.top()>a[i])

		{

			sum2-=q2.top();

			sum2+=a[i];

			q2.pop();

			q2.push(a[i]);

		}

		dp2[i]=sum2;

	}

	long long ans=-0x3f3f3f3f3f3f3f3f;

	for(int i=n;i<=2*n;i++)

	{

//		printf("%d %lld %lld\n",i,dp1[i],dp2[i]);

		ans=max(ans,dp1[i]-dp2[i+1]);

	}

	printf("%lld\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.896924239656907x):
#include<bits/stdc++.h>

using namespace std;

#define mod 1000000007

#define MOD(x) ((x)%mod)

int n,m;

long long a[300005];

long long b[300005];

long long c[300005];

long long sum1,sum2;

long long ans;

priority_queue<long long , vector<long long> , greater<int> >q1;

priority_queue<long long , vector<long long> , less<int> >q2;

int main()

{

	scanf("%d",&n);

	m=3*n;

	for(int i=1;i<=m;i++)

		scanf("%lld",&a[i]);

	for(int i=1;i<=m;i++)

	{

		if(q1.size()<n)

		{

			q1.push(a[i]);

			b[i]=b[i-1]+a[i];

		}

		else

		{

			if(a[i]>q1.top())

			{

				b[i]=b[i-1]-q1.top()+a[i];

				q1.pop();

				q1.push(a[i]);

			}

			else b[i]=b[i-1];			

		}

	}

	for(int i=m;i>=1;i--)

	{

		if(q2.size()<n)

		{

			q2.push(a[i]);

			c[i]=c[i+1]+a[i];

		}

		else

		{

			if(a[i]<q2.top())

			{

				c[i]=c[i+1]-q2.top()+a[i];

				q2.pop();

				q2.push(a[i]);

			}

			else c[i]=c[i+1];

		}

	}

	bool sign=0;

	for(int i=n;i<=2*n;i++)

	{

		if(sign==0)

		{

			ans=b[i]-c[i+1];

			sign=1;

		}

		else ans=max(ans,b[i]-c[i+1]);

	}

	printf("%lld",ans);

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define MAXN 100005

#define LL long long

#define INF 1e18

int N,M,S,T,u,v;

LL a,b,f=1e15,ans[MAXN];

LL Min(LL x,LL y)

{

	if(x>y) return y;

		return x;

}

struct graph{

	int cnt,head[MAXN],vis[MAXN];

	LL dis[MAXN];

	struct Edge

	{

		int next,to;LL dis;

	}edge[2*MAXN];

	queue<int> q;

	

	void addedge(int from,int to,LL dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	

	void spfa(int s)

	{

		for(int i=1;i<=N;i++)

			dis[i]=INF;

		memset(vis,0,sizeof(vis));

		q.push(s); vis[s]=1; dis[s]=0;

		while(!q.empty())

		{

			int x=q.front(); q.pop();

			vis[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) q.push(to),vis[to]=1;

				}

			}

		}

	}

}g1,g2;

int main()

{

	scanf("%d %d %d %d",&N,&M,&S,&T);

	for(int i=1;i<=M;i++)

	{

		scanf("%d %d %lld %lld",&u,&v,&a,&b);

		g1.addedge(u,v,a); g1.addedge(v,u,a);

		g2.addedge(v,u,b); g2.addedge(u,v,b);

	}

	g1.spfa(S); g2.spfa(T);

	ans[N+1]=INF;

	for(int i=N;i>=1;i--) ans[i]=Min(ans[i+1],g1.dis[i]+g2.dis[i]);

	for(int i=1;i<=N;i++)

		printf("%lld\n",f-ans[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4229004892258699x):
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+8;

int n,m,s,t;

long long ans[N];

struct node{

    int cnt,head[N];

    long long cost[N];

    bool flag[N];

    struct Edge {int next, to; long long cost;} edge[N*2];

	queue<int> q;

	void add(int from,int to,long long cost)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].cost=cost;

		head[from]=cnt;

	}

	void spfa(int s)

	{

		for(int i=1;i<=n;i++) cost[i]=1000000000000000000;

		memset(flag,0,sizeof(flag));

		q.push(s); flag[s]=1; cost[s]=0;

		while(!q.empty())

		{

			int x=q.front();

			q.pop();

			flag[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(cost[to]>cost[x]+edge[i].cost)

				{

					cost[to]=cost[x]+edge[i].cost;

					if(!flag[to]) q.push(to),flag[to]=1;

				}

			}

		}

	}

}s_to_i,i_to_t;

long long Min(long long x,long long y)

{

    if(x>y) return y;

    return x;

}

int main()

{

    cin>>n>>m>>s>>t;

    for(int i=1;i<=m;i++)

    {

        int u,v;

        long long yen,snu;

        cin>>u>>v>>yen>>snu;

        s_to_i.add(u,v,yen);

        i_to_t.add(u,v,snu);

        s_to_i.add(v,u,yen);

        i_to_t.add(v,u,snu);

    }

    s_to_i.spfa(s);

    i_to_t.spfa(t);

    ans[n]=s_to_i.cost[n]+i_to_t.cost[n];

    for(int i=n-1;i>0;i--) ans[i]=Min(ans[i+1],s_to_i.cost[i]+i_to_t.cost[i]);

    for(int i=1;i<=n;i++) printf("%lld\n",1000000000000000-ans[i]);

}
// Slower C++ solution:
#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;



#define MAXN 100000

int N,M;

struct Edge{

    int v,w[2];

    Edge(){}

    Edge(int a,int w1,int w2){

        v=a,w[0]=w1,w[1]=w2;

    }

};

vector<Edge> G[MAXN+5];



bool vis[MAXN+5];

long long dist[2][MAXN+5];

void SPFA(int S,int opt){

    memset(vis,0,sizeof vis);

    memset(dist[opt],0x3f,sizeof dist[opt]);

    queue<int> Q;Q.push(S);

    dist[opt][S]=0;vis[S]=1;

    while(!Q.empty()){

        int u=Q.front();

        vis[u]=0;Q.pop();

        for(int i=0;i<int(G[u].size());i++){

            int v=G[u][i].v,w=G[u][i].w[opt];

            if(dist[opt][v]>dist[opt][u]+w){

                dist[opt][v]=dist[opt][u]+w;

                if(!vis[v]){

                    vis[v]=1;

                    Q.push(v);

                }

            }

        }

    }

}



long long Ans[MAXN+5];

int main(){

    int S,T;

    scanf("%d%d%d%d",&N,&M,&S,&T);

    for(int i=1;i<=M;i++){

        int u,v,w1,w2;

        scanf("%d%d%d%d",&u,&v,&w1,&w2);

        G[u].push_back(Edge(v,w1,w2));

        G[v].push_back(Edge(u,w1,w2));

    }

    SPFA(S,0);

    SPFA(T,1);

    Ans[N]=dist[0][N]+dist[1][N];

    for(int i=N-1;i>=1;i--)

        Ans[i]=min(Ans[i+1],dist[0][i]+dist[1][i]);

    for(int i=1;i<=N;i++)

        printf("%lld\n",1000000000000000ll-Ans[i]);

}


// Faster C++ solution for the same problem (measured speedup: 3.0086080025249644x):
//SPFA

#include<bits/stdc++.h>

#define ll long long

#define INF 1e18

#define MAXN 100005



ll min(ll x,ll y){if(x<y) return x;return y;}

	

	int n,m,s,t,u,v;

	ll a,b,f=1e15,ans[MAXN];

	

struct Graph

{

	int cnt,head[MAXN],vis[MAXN];

	ll dis[MAXN];

	

	struct Edge{int next,to;ll dis;}edge[MAXN*2];

	

	std::queue<int> q;

	

	void addedge(int from,int to,ll dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	void spfa(int s)

	{

		for(int i=1;i<=n;i++) dis[i]=INF;

		memset(vis,0,sizeof(vis));

		q.push(s);vis[s]=1;dis[s]=0;

		while(!q.empty())

		{

			int x=q.front();q.pop();

			vis[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) q.push(to),vis[to]=1;

				}

			}

		}

	}

}g1,g2;



int main()

{

	scanf("%d%d%d%d",&n,&m,&s,&t);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d%lld%lld",&u,&v,&a,&b);

		g1.addedge(u,v,a);g1.addedge(v,u,a);

		g2.addedge(v,u,b);g2.addedge(u,v,b);

	}

	g1.spfa(s);g2.spfa(t);

	ans[n+1]=INF;

	for(int i=n;i>=1;i--) ans[i]=min(ans[i+1],g1.dis[i]+g2.dis[i]);

	for(int i=1;i<=n;i++) printf("%lld\n",f-ans[i]);

}
// Slower C++ solution:
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<vector>

#include<queue>

using namespace std;

const int MAXN=1e5;

struct EDGE{

	int v,val[2];

	EDGE(){}

	EDGE(int c,int d,int e){v=c;val[0]=d;val[1]=e;}

};

int n_cty,n_edg,s,t;

vector<EDGE>lnk[MAXN+5];

long long dist[2][MAXN+5],ans[MAXN+5];//0:yen start->i   1:snuuk end->i

bool vis[MAXN+5];

void SPFA(int start,int kind)

{

	memset(vis,0,sizeof vis);

	fill(dist[kind],dist[kind]+n_cty+3,1e15);

	queue<int> que;que.push(start);

	dist[kind][start]=0;vis[start]=true;

	while(!que.empty())

	{

		int u=que.front();que.pop();

		for(int i=0;i<lnk[u].size();i++)

		{

			int v=lnk[u][i].v,val=lnk[u][i].val[kind];

			if(dist[kind][v]>dist[kind][u]+val)

			{

				dist[kind][v]=dist[kind][u]+val;

				if(!vis[v])

					vis[v]=true,que.push(v);

			}

		}

		vis[u]=false;

	}

}

struct DEQUE{

	int val,date;

	DEQUE(){}

	DEQUE(int a,int b){val=a;date=b;}

};

int main()

{

	scanf("%d%d%d%d",&n_cty,&n_edg,&s,&t);

	for(int i=0;i<n_edg;i++)

	{

		int u,v,a,b;scanf("%d%d%d%d",&u,&v,&a,&b);

		lnk[u].push_back(EDGE(v,a,b));

		lnk[v].push_back(EDGE(u,a,b));

	}

	SPFA(s,0);

	SPFA(t,1);

	fill(ans+1,ans+n_cty+3,1e15);

	for(int i=n_cty;i>=1;i--)

	{

		long long val=dist[0][i]+dist[1][i];

		ans[i]=min(ans[i+1],val);

	}

	for(int i=1;i<=n_cty;i++)

		printf("%lld\n",(long long)1e15-ans[i]);

	/*

	deque<DEQUE> low;

	for(int i=1;i<=n_cty;i++)

	{

		int val=dist[0][i]+dist[1][i];

		while(!low.empty() && low.back().val>val) low.pop_back();

		low.push_back(DEQUE(val,i));

	}

	for(int i=1;i<=n_cty;i++)

	{

		while(!low.empty() && low.front().date<i) low.pop_front();

		printf("%lld\n",(long long)1e15-low.front().val);

	}

	*/

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.019660608708646x):
//SPFA

#include<bits/stdc++.h>

#define ll long long

#define INF 1e18

#define MAXN 100005



ll min(ll x,ll y){if(x<y) return x;return y;}

	

	int n,m,s,t,u,v;

	ll a,b,f=1e15,ans[MAXN];

	

struct Graph

{

	int cnt,head[MAXN],vis[MAXN];

	ll dis[MAXN];

	

	struct Edge{int next,to;ll dis;}edge[MAXN*2];

	

	std::queue<int> q;

	

	void addedge(int from,int to,ll dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	void spfa(int s)

	{

		for(int i=1;i<=n;i++) dis[i]=INF;

		memset(vis,0,sizeof(vis));

		q.push(s);vis[s]=1;dis[s]=0;

		while(!q.empty())

		{

			int x=q.front();q.pop();

			vis[x]=0;

			for(int i=head[x];i;i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) q.push(to),vis[to]=1;

				}

			}

		}

	}

}g1,g2;



int main()

{

	scanf("%d%d%d%d",&n,&m,&s,&t);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d%lld%lld",&u,&v,&a,&b);

		g1.addedge(u,v,a);g1.addedge(v,u,a);

		g2.addedge(v,u,b);g2.addedge(u,v,b);

	}

	g1.spfa(s);g2.spfa(t);

	ans[n+1]=INF;

	for(int i=n;i>=1;i--) ans[i]=min(ans[i+1],g1.dis[i]+g2.dis[i]);

	for(int i=1;i<=n;i++) printf("%lld\n",f-ans[i]);

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<queue>



using namespace std;

#define int long long

using P = pair<int,int>;

int N,M,S,T;

struct edge{int to,idx;};//行先とindex

vector<edge> G[101000];//グラフ,二次元配列っぽくあつかってる？

vector<int> A(101000),B(101000);//円とすぬけ



vector<int> dijkstra(int s,vector<int>& cost){

    vector<int> dist(101000,1e18); dist[s] = 0;//距離を無限に

    priority_queue<P,vector<P>,greater<P>> Q;

    Q.push({0,s});



    while(!Q.empty()){

        P p = Q.top(); Q.pop();

        if(dist[p.second] < p.first) continue;

        for(auto & e : G[p.second]){

            if(dist[e.to] > dist[p.second] + cost[e.idx]){

                dist[e.to] = dist[p.second] + cost[e.idx];

                Q.push({dist[e.to],e.to});

            }

        }

    }

    return dist;

}

signed main(){

    cin>>N>>M>>S>>T;

    for(int i=0;i<M;++i){

        int u,v;

        cin>>u>>v>>A[i]>>B[i];

        G[u].push_back({v,i});//駅uからつながるvと年i

        G[v].push_back({u,i});//駅vからつながる

    }



    auto yen = dijkstra(S,A);

    auto snuke = dijkstra(T,B);



    int ans = 0;

    vector<int> res;

    int base = 1e15;

    for(int i=N;i>0;--i){

        ans = max(ans,base - yen[i] - snuke[i]);

        res.push_back(ans);

    }



    for(int i = res.size()-1;i>=0;--i) cout<<res[i]<<endl;



}


// Faster C++ solution for the same problem (measured speedup: 1.3491716229452604x):
#include<bits/stdc++.h>

using namespace std;

#define int long long

using P = pair<int,int>;



struct edge{int to,idx;};

vector<edge> G[100100];



vector<int> dijkstra(int s,vector<int>& cost){

    vector<int> dist(100100,1e18); dist[s] = 0;

    priority_queue<P,vector<P>,greater<P>> Q;

    Q.push({0,s});

    while(!Q.empty()){

        P p = Q.top(); Q.pop();

        if(dist[p.second] < p.first) continue;

        for(auto &e : G[p.second]){

            if(dist[e.to] > dist[p.second] + cost[e.idx]){

                dist[e.to] = dist[p.second] + cost[e.idx];

                Q.push({dist[e.to],e.to});

            }

        }

    }

    return dist;

}



signed main(){

    int N,M,S,T;

    cin>>N>>M>>S>>T;

    vector<int> A(M),B(M);

    for(int i=0;i<M;++i){

        int u,v; cin>>u>>v>>A[i]>>B[i];

        G[u].push_back({v,i});

        G[v].push_back({u,i});

    }



    auto yen = dijkstra(S,A);

    auto snuuk = dijkstra(T,B);



    int ans = 0;

    vector<int> res;



    for(int i=N;i>0;--i){

        ans = max(ans,(int)1e15-yen[i]-snuuk[i]);

        res.push_back(ans);

    }



    for(int i=N-1;i>=0;--i) cout<<res[i]<<endl;

}
// Slower C++ solution:
#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;



#define MAXN 100000

int N,M;

struct Edge{

    int v,w[2];

    Edge(){}

    Edge(int a,int w1,int w2){

        v=a,w[0]=w1,w[1]=w2;

    }

};

vector<Edge> G[MAXN+5];



bool vis[MAXN+5];

long long dist[2][MAXN+5];

void SPFA(int S,int opt){

    memset(vis,0,sizeof vis);

    memset(dist[opt],0x3f,sizeof dist[opt]);

    queue<int> Q;Q.push(S);

    dist[opt][S]=0;vis[S]=1;

    while(!Q.empty()){

        int u=Q.front();

        vis[u]=0;Q.pop();

        for(int i=0;i<int(G[u].size());i++){

            int v=G[u][i].v,w=G[u][i].w[opt];

            if(dist[opt][v]>dist[opt][u]+w){

                dist[opt][v]=dist[opt][u]+w;

                if(!vis[v]){

                    vis[v]=1;

                    Q.push(v);

                }

            }

        }

    }

}



long long Ans[MAXN+5];

int main(){

    int S,T;

    scanf("%d%d%d%d",&N,&M,&S,&T);

    for(int i=1;i<=M;i++){

        int u,v,w1,w2;

        scanf("%d%d%d%d",&u,&v,&w1,&w2);

        G[u].push_back(Edge(v,w1,w2));

        G[v].push_back(Edge(u,w1,w2));

    }

    SPFA(S,0);

    SPFA(T,1);

    Ans[N]=dist[0][N]+dist[1][N];

    for(int i=N-1;i>=1;i--)

        Ans[i]=min(Ans[i+1],dist[0][i]+dist[1][i]);

    for(int i=1;i<=N;i++)

        printf("%lld\n",1000000000000000ll-Ans[i]);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.0087446169827343x):
#include <bits/stdc++.h>

#define LL long long

#define INF 1e18

#define MAXN 100005

 

LL min(LL x, LL y) {if(x<y) return x; return y;}

 

int n, m, s, t, u, v;

LL a, b, f=1e15, ans[MAXN];

 

struct Graph

{

	int cnt, head[MAXN], vis[MAXN];

	LL dis[MAXN];

	

	struct Edge {int next, to; LL dis;} edge[MAXN*2];

	

	std::queue<int> q;

	

	void addedge(int from, int to, LL dis)

	{

		edge[++cnt].next=head[from];

		edge[cnt].to=to;

		edge[cnt].dis=dis;

		head[from]=cnt;

	}

	

	void spfa(int s)

	{

		for(int i=1; i<=n; i++) dis[i]=INF;

		memset(vis, 0, sizeof(vis));

		q.push(s); vis[s]=1; dis[s]=0;

		while(!q.empty())

		{

			int x=q.front(); q.pop();

			vis[x]=0;

			for(int i=head[x]; i; i=edge[i].next)

			{

				int to=edge[i].to;

				if(dis[to]>dis[x]+edge[i].dis)

				{

					dis[to]=dis[x]+edge[i].dis;

					if(!vis[to]) q.push(to), vis[to]=1;

				}

			}

		}

	}

} g1, g2;

  

int main()

{

	

	scanf("%d%d%d%d", &n, &m, &s, &t);

	for(int i=1; i<=m; i++)

	{

		scanf("%d%d%lld%lld", &u, &v, &a, &b);

		g1.addedge(u, v, a); g1.addedge(v, u, a);

		g2.addedge(v, u, b); g2.addedge(u, v, b);

	}

	g1.spfa(s);  g2.spfa(t);

	ans[n+1]=INF;

	for(int i=n; i>=1; i--) ans[i]=min(ans[i+1], g1.dis[i]+g2.dis[i]);

	for(int i=1; i<=n; i++) printf("%lld\n", f-ans[i]);

}