#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lc now<<1
#define rc now<<1|1
const int M=1e5+5;
struct dian{
	int l,r,sum,add;
}f[M<<2|1];
int a[M];
void pushup(int now){
	f[now].sum=f[lc].sum+f[rc].sum;
}
void build(int now,int l,int r){
	f[now]={l,r,a[l],0};
	if(l==r)return ;
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(now);
}
void pushdown(int now){
	if(f[now].add){
		f[lc].sum+=(f[lc].r-f[lc].l+1)*f[now].add;
		f[rc].sum+=(f[rc].r-f[rc].l+1)*f[now].add;
		f[lc].add+=f[now].add;
		f[rc].add+=f[now].add;
		f[now].add=0;
	} 
}
void modi(int now,int x,int y,int k){
	if(x<=f[now].l&&y>=f[now].r){
		f[now].sum+=(f[now].r-f[now].l+1)*k;
		f[now].add+=k;
		return;
	}
	pushdown(now);
	int mid=f[now].l+f[now].r>>1;
	if(x<=mid)modi(lc,x,y,k);
	if(y>mid)modi(rc,x,y,k);
	pushup(now);
}
int que(int now,int x,int y){
	if(x<=f[now].l&&y>=f[now].r)
		return f[now].sum;
	int mid=f[now].l+f[now].r>>1;
	pushdown(now);
	int sum=0;
	if(x<=mid)sum+=que(lc,x,y);
	if(y>mid)sum+=que(rc,x,y);
	return sum;
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	cin>>a[i];
	build(1,1,n);
	while(m--){
		int op,x,y,k;
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			modi(1,x,y,k);
		}
		else {
			cin>>x>>y;
			cout<<que(1,x,y)<<'\n';
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e5 + 5;
int a[M], cnt = 1, vis[M];
int n, m, s, t;
int head[M], pre[M], mf[M], dis[M];
struct dian
{
    int to, c, w, ne;
} f[M];
int cost, flow;
void add(int x, int y, int c, int w)
{
    f[++cnt].to = y;
    f[cnt].c = c;
    f[cnt].w = w;
    f[cnt].ne = head[x];
    head[x] = cnt;
    f[++cnt].to = x;
    f[cnt].c = 0;
    f[cnt].w = -w;
    f[cnt].ne = head[y];
    head[y] = cnt;
}
int bfs()
{
    for (int i = 1; i <= n; ++i)
        mf[i] = 0;
    mf[s] = 1e18;
    for (int i = 1; i <= n; ++i)
        dis[i] = 1e18;
    dis[s] = 0;
    queue<int> p;
    p.push(s);
    vis[s] = 1;
    while (!p.empty())
    {
        int t = p.front();
        p.pop();
        vis[t] = 0;
        for (int i = head[t]; i; i = f[i].ne)
        {
            int to = f[i].to, c = f[i].c, w = f[i].w;
            if (c && dis[t] + w < dis[to])
            {
                dis[to] = dis[t] + w;
                mf[to] = min(mf[t], c);
                pre[to] = i;
                if (!vis[to])
                    vis[to] = 1, p.push(to);
            }
        }
    }
    return mf[t] > 0;
}
void ek()
{
    while (bfs())
    {
        int now = t;
        while (now != s)
        {
            int q = pre[now];
            f[q].c -= mf[t];
            f[q ^ 1].c += mf[t];
            now = f[q ^ 1].to;
        }
        flow += mf[t];
        cost += mf[t] * dis[t];
    }
}
void solve()
{
    cin >> n >> m >> s >> t;
    cnt = 1;
    while (m--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
    }
    ek();
    cout << flow << ' ' << cost;
    for (int i = 1; i <= n; ++i)
    {
        vis[i] = head[i] = mf[i] = pre[i] = dis[i] = 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int T = 1;
    // cin>>T;
    while (T--)
        solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long inf=1e18;
const int M=1e6+5;
int n,m,s,t;
int dis[M],now[M],head[M]; 
int cnt=1;
struct node {
    int to,net,w;
} e[M];

inline void add(int u,int v,int w) {
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].net=head[u];
    head[u]=cnt;
	
    e[++cnt].to=u;
    e[cnt].w=0;
    e[cnt].net=head[v];
    head[v]=cnt;
}

inline int bfs() {  //在惨量网络中构造分层图 
    for(int i=1;i<=n;i++) dis[i]=inf;
    queue<int> q;
    q.push(s);
    dis[s]=0;
    now[s]=head[s];
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].net) {
            int v=e[i].to;
            if(e[i].w>0&&dis[v]==inf) {
                q.push(v);
                now[v]=head[v];
                dis[v]=dis[x]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

inline int dfs(int x,long long sum) {  //sum是整条增广路对最大流的贡献
    if(x==t) return sum;
    long long k,res=0;  //k是当前最小的剩余容量 
    for(int i=now[x];i&&sum;i=e[i].net) {
        now[x]=i;  //当前弧优化 
        int v=e[i].to;
        if(e[i].w>0&&(dis[v]==dis[x]+1)) {
            k=dfs(v,min(sum,e[i].w));
            if(k==0) dis[v]=inf;  //剪枝，去掉增广完毕的点 
            e[i].w-=k;
            e[i^1].w+=k;
            res+=k;  //res表示经过该点的所有流量和（相当于流出的总量） 
            sum-=k;  //sum表示经过该点的剩余流量 
        }
    }
    return res;
}

void solve()
{
    cin>>n>>m>>s>>t;
    cnt=1;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    int ans=0;
    while(bfs()) {
        ans+=dfs(s,inf);  //流量守恒（流入=流出） 
    }
    cout<<ans;
    for (int i=0;i<=cnt+n;++i)
    {
        dis[i]=now[i]=head[i]=0;
    }
    cnt=1;
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 2e6 + 5;
int vis[M], ans[M];
struct edge
{
    int to, w;
};

vector<edge> f[M];
void add(int x, int y, int l)
{
    f[x].push_back({y, l});
}
void dij(int s, int n)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p;
    for (int i = 1; i <= n; i++)
        ans[i] = 1e18;
    ans[s] = 0;
    p.push({0, s});
    while (!p.empty())
    {
        auto [dis, id] = p.top();
        p.pop();
        if (vis[id])
            continue;
        vis[id] = 1;
        for (auto [y, w] : f[id])
        {
            if (w + ans[id] < ans[y])
            {
                ans[y] = w + ans[id];
                p.push({ans[y], y});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    for (int i = 1; i <= n; ++i)
    {
        f[i].clear();
        vis[i] = 0;
    }
}
void solve()
{
    int n, m, s, x, y, l;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> l;
        add(x, y, l);
    }
    dij(s, n);
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
        solve();

    return 0;
}