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 first, ll t):to(to),cost(first),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 first,d; cin >> first >> d;
        City.emplace_back(first,d);
        G[i].emplace_back(i,-first,d);
    }
}


// struct point{
//     ll first,second;
//     point(ll first=0, ll i=0):first(first),second(i){}
//     bool operator<(const point& p1) { return first < p1.first; } 
// };

// bool operator<(const point& p1, const point& p2) { return p1.first < p2.first; } 
using ppll = pair<ll, pll>;

vector<ll> memo;
ll dijkstra(){
    // if(memo[t]) return memo[t];
    priority_queue<ppll,vector<ppll>,greater<ppll> > pq;
    vector<bool> visited(N,false);
    vector<vector<ll> > dist(N,vector<ll>(A*N,INT_INF));
    int cnt=0;
    S = min(S,A*(N-1));
    dist[0][S] = 0; 
    pq.emplace(0,S,0);
    while(!pq.empty()){
        ll t;
        pll cur;
        tie(t,cur) = pq.top();
        pq.pop();
        // if(cur.second==t) return memo[cur.second] = cur.t;
        if(!visited[cur.second]) {
            cnt++;
            memo[cur.second] = t;
            }
        if(cnt==N) break;
        visited[cur.second] = true;
        if(t>dist[cur.second][cur.first]) continue;
        for(auto u:G[cur.second]){
            if(u.cost<=cur.first){
                pll next = cur;
                ll nt = t+u.time;
                next.second = u.to;
                next.first -= u.cost;
                next.first = min(next.first, S);
                if(dist[next.second][next.first] < nt) continue;
                dist[next.second][next.first] = nt;
                pq.emplace(nt,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, std::pair<long long int, long long int> >; _Args = {int, long long int&, int}; _Tp = std::pair<long long int, std::pair<long long int, long long int> >]':
/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, std::pair<long long int, long long int> >; _Args = {int, long long int&, int}; _Tp = std::pair<long long int, std::pair<long long int, long long int> >; allocator_type = std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >]'
  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, std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >; reference = std::pair<long long int, std::pair<long long int, long long int> >&]'
  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, std::pair<long long int, long long int> >; _Sequence = std::vector<std::pair<long long int, std::pair<long long int, long long int> > >; _Compare = std::greater<std::pair<long long int, std::pair<long long int, long long int> > >]'
  754 |           c.emplace_back(std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:101:15:   required from here
  101 |     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, std::pair<long long int, long long int> >::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<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_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 = std::pair<long long int, long long int>]'
  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<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<long long int, long long int>, _U2>::value)), long long int, std::pair<long long int, long long int> >::_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 = std::pair<long long int, long long int>]'
  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 = std::pair<long long int, long long int>]'
  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 = std::pair<long long int, long long int>]'
  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<std::pair<long long int, long long int>, _U2>, std::__not_<std::is_constructible<std::pair<long long int, long long int>, const _U1&> >, std::__not_<std::is_convertible<_U2, std::pair<long long int, long long int> > > >::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 = std::pair<long long int, long long int>]'
  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<std::pair<long long int, long long int>, _U2>, std::__not_<std::is_constructible<std::pair<long long int, long long int>, const _U1&> >, std::is_convertible<_U2, std::pair<long long int, long long int> > >::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 = std::pair<long long int, long long int>]'
  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<std::pair<long long int, long long int> >, 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>