Language: C++

/*
 
dunjen_master
 
*/
 
 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
 
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
 
using namespace std;
 
const int MAX_N = int(1e6) + 10;
const long long int MOD=1e9+7;
const long long int INF=1e18;
 
typedef long long int ll;
typedef unsigned long long int llu;
 
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

inline ll mul(ll a,ll b){

    a=(a+MOD)%MOD;
    b=(b+MOD)%MOD;
    ll c=a*b;
    c=(c+MOD)%MOD;
    return c;
}
inline ll add(ll a,ll b){
    a=(a+MOD)%MOD;
    b=(b+MOD)%MOD;
    ll ans=(a+b);
    ans=(ans+MOD)%MOD;
    return ans;
}
ll power(ll a,ll b,ll c=0){
    ll ans=1;
    while(b){
        if(b&1){
            ans=mul(ans,a);
        }
        a=mul(a,a);
        b=b/2;
    }
    return ans;
}
template<class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &P){
    in >> P.first >> P.second;
    return in;
}
 
template<class T1, class T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &P){
    out << "(" << P.first << ", " << P.second << ")";
    return out;
}
template<class T>
istream &operator>>(istream &in, vector<T> &arr){
    for(auto &x: arr) in >> x;
    return in;
}
template<class T>
ostream &operator<<(ostream &out, const vector<T> &arr){
    for(auto &x: arr) out << x << ' '; cout << "\n";
    return out;
}
template<class T>
istream &operator>>(istream &in, deque<T> &arr){
    for(auto &x: arr) in >> x;
    return in;
}
template<class T>
ostream &operator<<(ostream &out, const deque<T> &arr){
    for(auto &x: arr) out << x << ' '; cout << "\n";
    return out;
}
mt19937 rnd(time(0));
 
inline ll gcd(ll a,ll b){
    while(b)a%=b,swap(a,b);
    return a;
}
  

 
#define all(x) (x).begin(),(x).end()

/* ordered_set A;
   A.insert(x);
   A.erase(x);
   A.order_of_key(x) // no of elements less than (<) x
   *A.find_by_order(k-1) // kth smallest element
*/
// int n;
// ll dp[200005][205];
// ll ans=0;
// int a[200005];
// int req;
// ll neg=-1e15;


// ll fun(int indx,int last){
//    // cout<<indx<<" "<<last<<" "<<req<<endl;
//     if(indx==n){
//         if(last==req){
//             return 0;
//         }else{
//             return neg;
//         }
//     }

//     if(dp[indx][last]!=-1){
//         return dp[indx][last];
//     }
    
//     ll ans=neg;

//     ans=max(ans,fun(indx+1,last));

//     if(last==0)ans=max(ans,1+fun(indx+1,a[indx]));
//     if(last==a[indx])ans=max(ans,1+fun(indx+1,a[indx]));
//     if(a[indx]==req)ans=max(ans,1+fun(indx+1,a[indx]));

//     return dp[indx][last]=ans;


// }



int n,m;
ll s;
int x,y;
int a;
ll b;

vector<pair<int,pair<int,ll> > >v[55];
ll dis[55][4555];

ll c[55];
ll d[55];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m>>s;

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

        cin>>x>>y>>a>>b;

        v[x].push_back({y,{a,b}});
        v[y].push_back({x,{a,b}});
    }

    for(int i=1;i<=n;i++){
        cin>>c[i]>>d[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=4500;j++){
            dis[i][j]=1e18;
        }
    }
    
    set<pair<ll,pair<ll,int> > >ss;
    pair<ll,pair<ll,int> >p;
    ss.insert({0,{s,1}});
    dis[1][s]=0;

    while(!ss.empty()){
        p=*(ss.begin());
        ss.erase(ss.begin());

        int x=p.second.second;
        ll silvers=p.second.first;
        ll dd=p.first;

        if(dd>dis[x][silvers])continue;

        for(auto it:v[x]){

            int y=it.first;
            int a=it.second.first;
            ll b=it.second.second;

            if(silvers-a>=0 && dis[x][silvers]+b<dis[y][silvers-a]){
                  dis[y][silvers-a]=dis[x][silvers]+b;
                  ss.insert({dis[y][silvers-a],{silvers-a,y}});
            }


        }

        ll silverss=min(4500LL,silvers+c[x]);
        if(dis[x][silvers]+d[x]<dis[x][silverss]){
            dis[x][silverss]=dis[x][silvers]+d[x];
            ss.insert({dis[x][silverss],{silverss,x}});
        }
    }

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

        ll ans=1e18;

        for(int j=0;j<=4500;j++){
            ans=min(ans,dis[i][j]);
        }

        cout<<ans<<"\n";
    }

 
    
 

   

   
    

    

    

  
    



    


    
    
    
    
 
    
}

    

    
 
    



Compiler output:
In file included from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:12:
/usr/include/c++/14/bits/allocator.h: In destructor 'std::_Vector_base<std::pair<int, std::pair<int, long long int> >, std::allocator<std::pair<int, std::pair<int, long long int> > > >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/14/bits/allocator.h:182:7: error: inlining failed in call to 'always_inline' 'std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<int, std::pair<int, long long int> >]': target specific option mismatch
  182 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/stl_vector.h:132:14: note: called from here
  132 |       struct _Vector_impl
      |              ^~~~~~~~~~~~