Language: C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 2019;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N, M, S;
  cin >> N >> M >> S;
  vl U(M), V(M), A(M), B(M), C(N), D(N);
  rep(i, M) {
    cin >> U[i] >> V[i] >> A[i] >> B[i];
    --U[i], --V[i];
  }
  rep(i, N) cin >> C[i] >> D[i];
  
  vector<pair<ll,ll>> G[N];
  pair<ll,ll> u, v;
  rep(i, M) {
    u.first = U[i];
    v.first = V[i];
    u.second = i;
    v.second = i;
    G[U[i]].push_back(v);
    G[V[i]].push_back(u);
  }
  
  set<pair<ll,pair<ll,ll>>> Case;
  pair<ll,ll> _;
  _.first = 0;
  _.second = S;
  pair<ll,pair<ll,ll>> zero;
  zero.first = 0;
  zero.second = _;
  pair<ll,pair<ll,ll>> next;
  bool over=1;
  while(over) for(pair<ll,pair<ll,ll>> i: Case) {
    for(pair<ll,ll> j: G[i.second.first]) {
      next.first = i.first + B[j.second];
      next.second.first = j.first;
      next.second.second = i.second.second - A[j.second];
      Case.insert(j);
    }
    
    i.first += D[i.second.first];
    i.second.second += C[i.seond.first];
    Case.insert(i);
    if(i.first >= INF/5) over = 0;
  }
  
  vl ans(N);
  Sort(All(Case));
  for(pair<ll,pair<ll,ll>> i: Case) {
    if(ans[i.second.first]==0) ans[i.second.first] = i.first;
  }
  rep2(i, N-1) cout << ans[i] << newl;
  return 0;
}



/*
  pair([time],pair([place],[silver]))
*/

Compiler output:
a.cc: In function 'int main()':
a.cc:63:18: error: no matching function for call to 'std::set<std::pair<long long int, std::pair<long long int, long long int> > >::insert(std::pair<long long int, long long int>&)'
   63 |       Case.insert(j);
      |       ~~~~~~~~~~~^~~
In file included from /usr/include/c++/14/set:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:158,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_set.h:568:9: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >]'
  568 |         insert(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~
/usr/include/c++/14/bits/stl_set.h:568:9: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_set.h:511:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<long long int, std::pair<long long int, long long int> > > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >, std::pair<long long int, std::pair<long long int, long long int> > >::rebind<std::pair<long long int, std::pair<long long int, long long int> > >; typename _Alloc::value_type = std::pair<long long int, std::pair<long long int, long long int> >; value_type = std::pair<long long int, std::pair<long long int, long long int> >]'
  511 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:511:32: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'const std::set<std::pair<long long int, std::pair<long long int, long long int> > >::value_type&' {aka 'const std::pair<long long int, std::pair<long long int, long long int> >&'}
  511 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_set.h:520:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(value_type&&) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<long long int, std::pair<long long int, long long int> > > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, std::pair<long long int, long long int> > >, std::pair<long long int, std::pair<long long int, long long int> > >::rebind<std::pair<long long int, std::pair<long long int, long long int> > >; typename _Alloc::value_type = std::pair<long long int, std::pair<long long int, long long int> >; value_type = std::pair<long long int, std::pair<long long int, long long int> >]'
  520 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:520:27: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'std::set<std::pair<long long int, std::pair<long long int, long long int> > >::value_type&&' {aka 'std::pair<long long int, std::pair<long long int, long long int> >&&'}
  520 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_set.h:548:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(const_iterator, const value_type&) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >; iterator = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<long long int, std::pair<long long int, long long int> > > >::const_iterator; const_iterator = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<long long int, std::pair<long long int, long long int> > > >::const_iterator; value_type = std::pair<long long int, std::pair<long long int, long long int> >]'
  548 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:548:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_set.h:553:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(const_iterator, value_type&&) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >; iterator = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<long long int, std::pair<long long int, long long int> > > >::const_iterator; const_iterator = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<long long int, std::pair<long long int, long long int> > > >::const_iterator; value_type = std::pair<long long int, std::pair<long long int, long long int> >]'
  553 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:553:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_set.h:580:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >]'
  580 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_set.h:580:43: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'std::initializer_list<std::pair<long long int, std::pair<long long int, long long int> > >'
  580 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_set.h:600:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::insert_return_type std::set<_Key, _Compare, _Alloc>::insert(node_type&&) [with _Key = std::pair<long long int, std::pair<long long int, long long int> >; _Compare = std::less<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> > >; insert_return_type = std::_Rb_tree<std::pair<long long int, std::pair<long long int, long long int> >, std::pair<long long int, std::pair<long long int, long long int> >, std::_Identity<std::pair<long long int, std::pair<long long int, long long int> > >, std::less<std::pair<long long int, std::pair<long long int, long long int> > >, std::allocator<std::pair<lo