Language: C++

#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
    #include <filesystem>
    namespace fs = std::filesystem;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
static mt19937 _g(time(nullptr));
 
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N,M;
ll S;

struct edge{
    ll to,cost,time;
    edge(ll to, ll c, ll t):to(to),cost(c),time(t){}
};

vector<vector<edge>> G;
ll A=0;
vector<pll> City;
vector<vector<ll> > costs;
vector<vector<ll> > times;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path __p = __FILE__;
        fs::path __input, __output;
        __input = __output = __p.parent_path();
        __input += string("/input/") + string(__p.stem()) + string(".txt");
        __output += string("/output/") + string(__p.stem()) + string(".txt");
        freopen(__input.c_str(), "r", stdin);
        freopen(__output.c_str(), "w", stdout);
    #endif
    cin >> N >> M >> S;
    G.resize(N);
    costs.assign(N,vector<ll>(N,INT_INF));
    times.assign(N,vector<ll>(N,INT_INF));

    for (int i = 0; i < M; i++)
    {
        int u,v;
        ll a,b;
        cin >> u >> v >> a >> b;
        u--,v--;
        costs[u][v] = costs[v][u] = a;
        times[u][v] = times[v][u] = b;
        G[u].emplace_back(v,a,b);
        G[v].emplace_back(u,a,b);
        A = max(A,a);
    }
    for (int i = 0; i < N; i++)
    {
        ll c,d; cin >> c >> d;
        City.emplace_back(c,d);
        G[i].emplace_back(i,-c,d);
    }
}

void chmin(ll &a, ll b){if(a<b) a=b;}

int wrong_solve(){
    vector<map<ll,ll>> dp(N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= 5000; j++)
        {
            dp[i][j] = INT_INF;
        }
        
    }
    for (int j = 0; j <= S; j++) dp[0][j] = 0;
    
    int l=0;
    while((S+l*City[0].first)<=5000) {
        dp[0][S+l*City[0].first] =  l*City[0].second;
        l++;
        }
    // DBG(dp[0])
    queue<int> q;
    vector<bool> visited(N,false);
    q.push(0);
    int cnt=0;
    while(!q.empty()){
        int cur;
        // ll money;
        // tie(money,cur) = q.front();
        cur = q.front();
        if(visited[cur]) cnt++;
        if(cnt>=3*N) break;
        visited[cur] = true;
        q.pop();
        for(auto next:G[cur]){
            // if(dp[next.to][money-next.cost] < dp[cur][money]+next.time) continue;
            for (int j = 0; j < 5000; j++)
            {
                if(dp[next.to][j]>dp[cur][j+next.cost]+next.time)
                dp[next.to][j]=dp[cur][j+next.cost]+next.time;
                if(dp[next.to][j+City[next.to].first]>(dp[next.to][j]+City[next.to].second))
                dp[next.to][j+City[next.to].first]=(dp[next.to][j]+City[next.to].second);
                // chmin(dp[next.to][j+City[next.to].first], (dp[next.to][j]+City[next.to].second));

            }
            // ll nem = money-next.cost;
            // chmin(dp[next.to][nem],dp[cur][money]+next.time);
            // chmin(dp[next.to][nem+City[next.to].first],dp[next.to][nem]+City[next.to].second);

            q.push(next.to);
            // q.emplace(nem, next.to);
        }
    }
    // DBG(dp)
    // auto cmp = [](const auto& l, const auto& r) { return l.second > r.second; };
    for (int i = 1; i < N; i++)
    {
        // SAY("a")
        // DBG(dp[i])
        ll ans = INT_INF;
        for (int j = 0; j < 100; j++)
        {
            ans = min(ans,dp[i][j]);
        }
        
        // auto itr = *min_element(dp[i].begin(),dp[i].end(),cmp);
        cout << ans << endl;
    }
    

    return 0;
}   

struct point{
    ll c,idx;
    point(ll c=0, ll i=0):c(c),idx(i){}
};

bool operator<(const point& p1, const point& p2) { return p1.c < p2.c; } 

using plst = pair<ll,point>;

vector<ll> memo;
ll dijkstra(){
    // if(memo[t]) return memo[t];
    priority_queue<plst,vector<plst>,greater<plst> > pq;
    vector<bool> visited(N,false);
    vector<vector<ll>> dist(N,vector<ll>(A*(N-1),INT_INF));
    int cnt=0;
    S = min(S,A*(N-1));
    pq.emplace(0,S,0);
    while(!pq.empty()){
        ll t;
        point cur;
        tie(t,cur) = pq.top();
        pq.pop();
        // if(cur.idx==t) return memo[cur.idx] = cur.t;
        if(!visited[cur.idx]) {
            cnt++;
            memo[cur.idx] = t;
            }
        if(cnt==N) break;
        visited[cur.idx] = true;
        if(t>dist[cur.idx][cur.c]) continue;
        for(auto u:G[cur.idx]){
            if(u.cost<=cur.c){
                point next = cur;
                ll nt = t+u.time;
                next.idx = u.to;
                next.c -= u.cost;
                next.c = min(next.c, S);
                if(dist[next.idx][next.c] < nt) continue;
                dist[next.idx][next.c] = nt;
                pq.emplace(t,next);
            }
        }
    }
    return -1;
}

int solve(){
    memo.assign(N,0);
    dijkstra();
    for (int i = 1; i < N; i++) cout << memo[i] << "\n";

    return 0;    
}

int main()
{
    input();
    solve();
    return 0;
}


Compiler output:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 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:1:
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<long long int, point>; _Args = {int, long long int&, int}; _Tp = std::pair<long long int, point>]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<long long int, point>; _Args = {int, long long int&, int}; _Tp = std::pair<long long int, point>; allocator_type = std::allocator<std::pair<long long int, point> >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/vector.tcc:117:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int, long long int&, int}; _Tp = std::pair<long long int, point>; _Alloc = std::allocator<std::pair<long long int, point> >; reference = std::pair<long long int, point>&]'
  117 |             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |                                      std::forward<_Args>(__args)...);
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:754:18:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::emplace(_Args&& ...) [with _Args = {int, long long int&, int}; _Tp = std::pair<long long int, point>; _Sequence = std::vector<std::pair<long long int, point> >; _Compare = std::greater<std::pair<long long int, point> >]'
  754 |           c.emplace_back(std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:171:15:   required from here
  171 |     pq.emplace(0,S,0);
      |     ~~~~~~~~~~^~~~~~~
/usr/include/c++/14/bits/new_allocator.h:191:11: error: no matching function for call to 'std::pair<long long int, point>::pair(int, long long int&, int)'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:913:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<point, _U2>::value)), long long int, point>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<point, _U2>::value)), long long int, point>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = point]'
  913 |         explicit constexpr pair(pair<_U1, _U2>&& __p)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:913:28: note:   candidate expects 1 argument, 3 provided
/usr/include/c++/14/bits/stl_pair.h:902:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<point, _U2>::value)), long long int, point>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<point, _U2>::value)), long long int, point>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = point]'
  902 |         constexpr pair(pair<_U1, _U2>&& __p)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:902:19: note:   candidate expects 1 argument, 3 provided
/usr/include/c++/14/bits/stl_pair.h:891:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && (! _ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = point]'
  891 |         explicit constexpr pair(_U1&& __x, _U2&& __y)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:891:28: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/stl_pair.h:881:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && _ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = point]'
  881 |         constexpr pair(_U1&& __x, _U2&& __y)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:881:19: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/stl_pair.h:869:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<long long int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<point, _U2>, std::__not_<std::is_constructible<point, const _U1&> >, std::__not_<std::is_convertible<_U2, point> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::__not_<std::is_convertible<_U2, _T2> > >::value, bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = point]'
  869 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:869:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:866:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  866 |                              bool> = false>
      |                                      ^~~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<long long int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<point, _U2>, std::__not_<std::is_constructible<point, const _U1&> >, std::is_convertible<_U2, point> >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::is_convertible<_U2, _T2> >::value, bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = point]'
  856 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:853:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  853 |                              bool> = true>
      |                                      ^~~~
/usr/include/c++/14/bits/stl_pair.h:843:9: note: candidate: 'template<class _U1, typename std::enable_if<std::__and_<std::__not_<std::is_reference<_Tp> >, std::is_pointer<point>, std::is_constructible<long long int, _U1>, std::__not_<std::is_constructible<long long int, const _U1&> >, std::__not_<std::is_convertible<_U1, long long int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, __zero_as_null_pointer_constant, ...) [with typename std::enable_if<std::__and_<std::__not_<std::is_reference<_U1> >, std::is_pointer<_T2>, std::is_constructible<_T1, _U1>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::__not_<std::is_convertible<_U1, _T1> > >::value, bool>::type <anonymous> = _U1; _T1 = long long int; _T2 = point]'
  843 |         pair(_U1&& __x, __zero_as_null_pointer_constant, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:843:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:840:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  840 |                              bool> = false>
      |                                      ^~~~~
/usr/include/c++/14/bits/stl_pair.h:830:9: note: candidate: 'template<class _U1, typename std::enable_if<std::__and_<std::__not_<std::is_reference<_Tp> >, std::is_pointer<point>, std::is_constructible<long long int, _U1>, std::__not_<std::is_constructible<long long int, const _U1&> >, std::is_convertible<_U1, long long int> >::value, bool>::