#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
#define vall(x) (x).begin(), (x).end()
using namespace std;
namespace atcoder {}
using namespace atcoder;
using lli = long long int;
void YESNO(bool), YesNo(bool);
template <class T1, class T2> bool chmin(T1 &l, const T2 &r);
template <class T1, class T2> bool chmax(T1 &l, const T2 &r);
#define int long long int
struct dijkstra {
  vector<vector<pair<lli, pair<lli, lli>>>> e;
  int n;
  lli inf = 1e18;
  dijkstra(int n) : n(n) { e.resize(n); }
  void add(int a, int b, lli c, lli k) {
    e[a].push_back(make_pair(b, make_pair(c, k)));
  }
  void biadd(int a, int b, lli c, lli k) {
    add(a, b, c, k);
    add(b, a, c, k);
  }
  vector<lli> get(int s) {
    vector<lli> dist(n, inf);
    dist[s] = 0;
    using p = pair<lli, lli>;
    priority_queue<p, vector<p>, greater<p>> que;
    que.push(make_pair(0, s));
    while (!que.empty()) {
      lli d = que.top().first;
      lli cur = que.top().second;
      que.pop();
      if (dist[cur] < d)
        continue;
      dist[cur] = d;
      for (auto s : e[cur]) {
        lli wei = s.second.first;
        lli k = s.second.second;
        lli to = s.first;
        lli t = dist[cur] + wei + (d % k ? k - dist[cur] % k : 0);
        if (dist[to] > t) {
          dist[to] = t;
          que.push(make_pair(t, to));
        }
      }
    }
    return dist;
  }
};
void solve(long long N, long long M, long long X, long long Y,
           std::vector<long long> A, std::vector<long long> B,
           std::vector<long long> T, std::vector<long long> K) {
  dijkstra dij(N);
  rep(i, M) { dij.biadd(A[i] - 1, B[i] - 1, T[i], K[i]); }
  auto t = dij.get(X - 1)[Y - 1];
  if (t >= 1e16) {
    cout << -1 << endl;
  } else {
    cout << t << endl;
  }
}
 
signed main() {
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  long long X;
  scanf("%lld", &X);
  long long Y;
  scanf("%lld", &Y);
  std::vector<long long> A(M);
  std::vector<long long> B(M);
  std::vector<long long> T(M);
  std::vector<long long> K(M);
  for (int i = 0; i < M; i++) {
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
    scanf("%lld", &T[i]);
    scanf("%lld", &K[i]);
  }
  solve(N, M, X, Y, std::move(A), std::move(B), std::move(T), std::move(K));
  return 0;
}
 
// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
 
template <class T1, class T2> bool chmin(T1 &l, const T2 &r) {
  return (l > r) ? (l = r, true) : false;
}
 
template <class T1, class T2> bool chmax(T1 &l, const T2 &r) {
  return (l < r) ? (l = r, true) : false;
}
 
template <class T1, class T2> void vadd(vector<T1> &v, T2 x) {
  for (auto &s : v)
    s += T2(x);
}
#include<bits/stdc++.h>
using namespace std;
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define ll 				long long
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define mii               map<ll,ll>
#define pqi             priority_queue<ll>			//max pq
#define pqd             priority_queue<ll,vi,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define MOD             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define pw(b,p)         pow(b,p) + 0.1
#define f(i,k,n)		for(ll i=k;i<n;i++)
#define fd(i,start,end)	for(ll i=start;i>=end;i--)

ll power(ll a, ll b, ll mod) {ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % mod; a = a * a % mod;} return res;}
ll power(ll a, ll b) {ll res = 1; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a ; a = a * a;} return res;}
ll min( ll a,  ll b) { return (a < b) ? a : b;}
ll max(ll a, ll b) {return (a > b) ? a : b;}
ll gcd (ll a, ll b) {if (a == 0) return  b; return gcd(b % a, a);}



void bwayne()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
}
// ll n;
// cin >> n;
// vi a(n);
// f(i, 0, n) {
// 	cin >> a[i];
// }

// vector<vi> a(n,vector<vi>(m,0));
// f(i,0,n){
// 	f(j,0,m){
// 		cin>>a[i][j];
// 	}
// }




void solve() {
	ll n;
	cin >> n;
	vi a(n + 1);
	mii m;
	f(i, 1, n + 1) {
		cin >> a[i];
		m[a[i]] = i;
	}
	vi ans;
	set<ll> ansset;
	fd(i, n, 2) {
		ll curr = m[i];
		// cout << curr << endl;
		if (curr < i) {
			while (curr < i) {
				ll one = curr;
				ll two = curr + 1;
				ll el1 = a[one];
				ll el2 = a[two];
				swap(a[one], a[two]);
				m[el2] = one;
				m[el1] = two;
				if (ansset.find(curr) != ansset.end()) {
					cout << -1;
					return;
				}
				ans.pb(curr);
				ansset.insert(curr);
				// cout << "&" << curr << endl;
				// f(i, 1, n + 1) {
				// 	cout << a[i] << " ";
				// }
				// cout << endl;
				curr++;
			}
		}
		else if (curr > i) {
			cout << -1;
			return;
		}
	}
	if (ans.size() != n - 1) {
		cout << -1;
		return;
	}
	f(i, 0, n - 1) {
		cout << ans[i] << endl;
	}



}
int main()
{
	bwayne();// remember
	ll t = 1;
	// cin >> t;

	for (ll tt = 1; tt <= t; tt++)
	{
		// cout << "Case #" << tt << ": ";
		solve();
	}

	return 0;
}