#include <bits/stdc++.h>
#define ri register int
#define fi first
#define se second
#define pb push_back
#define ppp pop_back
#define rez resize
using namespace std;
typedef unsigned int uit;
typedef long long ll;
typedef vector <int> poly;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
const int rlen = 1 << 20 | 5;
char buf[rlen], *ib = buf, *ob = buf;
#define gc() (((ib == ob) && (ob = (ib = buf) + fread(buf, 1, rlen, stdin))), ib == ob ? -1 : *ib++)
inline int read() {
  static int ans, f;
  static char ch;
  for (ans = 0, f = 1, ch = gc(); !isdigit(ch); f ^= ch == '-', ch = gc());
  for (; isdigit(ch); ans = ((ans << 2) + ans << 1) + (ch ^ 48), ch = gc());
  return f ? ans : -ans;
}
inline ll readl() {
  static ll ans;
  static int f;
  static char ch;
  for (ch = gc(), ans = 0, f = 1; !isdigit(ch); f ^= ch == '-', ch = gc());
  for (; isdigit(ch); ans = ((ans << 2) + ans << 1) + (ch ^ 48), ch = gc());
  return f ? ans : -ans;
}
inline int Read(char *s) {
  static int len;
  static char ch;
  for (ch = gc(), len = 0; !isalpha(ch); ch = gc());
  for (; isdigit(ch); s[++len] = ch, ch = gc());
  return len;
}
template <typename T> inline void ckmax(T &a, T b) {
  a = a > b ? a : b;
}
template <typename T> inline void ckmin(T &a, T b) {
  a = a < b ? a : b;
}
namespace modular {
  const int mod = 1e9 + 7;
  inline int add(int a, int b) {
    return a < mod - b ? a + b : a - mod + b;
  }
  inline int dec(int a, int b) {
    return a < b ? a - b + mod : a - b;
  }
  inline int mul(int a, int b) {
    return (ll) a * b % mod;
  }
  inline void Add(int &a, int b) {
    a = a < mod - b ? a + b : a - mod + b;
  }
  inline void Dec(int &a, int b) {
    a = a < b ? a - b + mod : a;
  }
  inline void Mul(int &a, int b) {
    a = (ll) a * b % mod;
  }
  inline int ksm(int a, int p) {
    static int ret;
    for (ret = 1; p; p >>= 1, Mul(a, a)) {
      (p & 1) && (Mul(ret, a), 1);
    }
    return ret;
  }
}  using namespace modular;
const int N = 1e5 + 5;
ll n;
inline ll calc(ll t) {
  ll x = t, y = n - t, sz = 0;
  x = t, y = n - t;
  ++sz;
  while (x >= 3 && y >= 3) {
    if (x > y) {
      ++sz;
      x -= y;
    } else  if (x < y) {
      ++sz;
      y -= x;
    }
    if (x == y) {
      break;
    }
  }
  return sz + x + y;
}
int main() {
  #ifdef ldxcaicai
  freopen("lx.in", "r", stdin);
  #endif
  double tt = (sqrt(5.0) - 1) / 2;
  n = readl();
  ll t, x, y;
  t = (ll) (tt * (double) n);
  for (ll i = max(0ll, t - 5000); i <= min(n, t + 5000); ++i) {
    if (calc(i) <= 130) {
      x = i, y = n - i;
      poly res;
      res.pb(3);
      while (x >= 3 && y >= 3) {
        if (x > y) {
          res.pb(3);
          x -= y;
        } else  if (x < y) {
          res.pb(4);
          y -= x;
        }
        if (x == y) {
          break;
        }
      }
      while (x) {
        --x;
        res.pb(1);
      }
      while (y) {
        --y;
        res.pb(2);
      }
      cout << res.size() << '\n';
      while (res.size()) {
        cout << res.back() << '\n';
        res.ppp();
      }
      return 0;
    }
  }
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vec;
using Graph = vector<vector<int>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;
const int inf=1e9+7;
  

struct edge { ll to, cost, time; };   //辺
int V;   //頂点数
const int MAX_V = 1000000;
vector<vector<edge>> G(MAX_V);
ll d[MAX_V];

void dijkstra(int s) {
    //greater<P>でfirstが小さい順に取り出せる
    //first:最短距離,second:頂点番号
    priority_queue<P, vector<P>, greater<P>> que;
    fill(d, d + V, INF);
    d[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first)continue;
        rep(i, G[v].size()) {
            edge e = G[v][i];
            ll sta=d[v];
            if(d[v]%e.time!=0){
              sta+=(e.time-d[v]%e.time);
            }
            if (d[e.to] > sta + e.cost) {
                d[e.to] = sta + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m,x,y;cin>>V>>m>>x>>y;
    x--,y--;
    rep(i,m){
      ll a,b,t,k;
      cin>>a>>b>>t>>k;
      a--;b--;
      G[a].push_back({b,t,k});
      G[b].push_back({a,t,k});
    }
    dijkstra(x);
    if(d[y]>=INF)cout<<-1<<endl;
    else cout<<d[y]<<endl;
    return 0;
}