// Atcoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES

#include<math.h>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
#include <sstream>



using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1e18)
#define MOD (1e9+7)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define all(x) (x).begin(),(x).end()
//#define int long long
typedef pair < ll, ll> P;

//元がintの分けたものを返す p[0]は1桁目
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
//桁数を返す
int digiter(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}
//元がstringの分けたものを返す d[0]は最高位
vector<int> convertstring(string s) {
	vector<int> d;
	ll n = s.size();
	reverse(s.begin(), s.end());
	rep(i, n) {
		d.push_back(s[i] - '0');
	}
	return d;
}

/*long double　は%Lf*/
//queue古い順,stack新しい
//bool operator<(const Info &another) const {return x > another.x;}//struct(構造体)内の比較演算子のオバーロード
string S; ll M; int d;
int32_t main() {
	cin >> S >> M;
	rep(i, S.size()) {
		chmax(d, S[i] - '0');
	}
	reverse(S.begin(), S.end());

	rep(i, S.size()) {
		if (pow(d + 1, i) > M) {

			cout << 0 << endl;
			return 0;
		}
	}
	ll su = 0;
	rep(i, S.size()) {
		su += ll(S[i] - '0') * pow(d + 1, i);
	}
	if (su > M) {
		cout << 0 << endl;
		return 0;
	}
	//cout << d << endl;
	ll ul = LINF+1LL; ll bl = d + 1;
	ul++;
	while (ul - bl > 1) {
		ll mid = (ul + bl) >> 1LL;
		ll sum = 0;
		rep(i, S.size()) {
			if (pow(mid, i) > M) {
				ul = mid;
				//cout << "work"<<mid << endl;
				break;
			}
		}
		if (ul == mid) {
			continue;
		}
		rep(i, S.size()) {
			sum += ll(S[i] - '0') * pow(mid, i);
			if (sum > M) {
				ul = mid;
				break;
			}

		}


		if (sum <= M) {
			bl = mid;
		}
		else {
			ul = mid;
		}
	}
	if (S.size() == 1) {
		cout << min(1LL, bl - d) << endl;
		return 0;
	}
	cout << bl - d << endl;


}
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl
 
#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()
 
#define pb push_back
#define ff first
#define ss second
#define hell 1000000007
 
#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 100009
 
ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
ll dist[N];
bool vis[N];
//ll parent[N];
vector<pair<ll,pii>> v[N];
void initialise()
{
	rep(i,1,N)
	{
		//parent[i]=-1;
		v[i].clear();
		dist[i]=LLONG_MAX;
		vis[i]=0;
	}
	return ;
}
ll dijkstra(ll src,ll dest)
{
	vis[src]=1;
	multiset<pii>s;
	s.insert({0,src});
	dist[src]=0;
	
	while(s.size())
	{
		auto it=s.begin();
		ll d=it->ff;
		ll num=it->ss;
		s.erase(it);

		vis[num]=1;
		rep(i,0,v[num].size())
		{

			if(vis[v[num][i].ff])
			continue;	


			// time for this

			ll tm;
			if(dist[num] % v[num][i].ss.ss == 0) {
				tm = dist[num] + v[num][i].ss.ff;
			}
			else {
				ll mc = dist[num]/ v[num][i].ss.ss;
				mc ++;
				mc *= v[num][i].ss.ss;

				tm = mc - dist[num];
				tm += v[num][i].ss.ff;
				tm += dist[num];
			}
			//tm += dist[num];

			if(tm >= dist[v[num][i].ff])
			continue;
			
			dist[v[num][i].ff]=tm;
			//parent[v[num][i].ff]=num;
			s.insert({tm,v[num][i].ff});
		}
	}
	return dist[dest];
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	initialise();
	ll n,m,source,dest;
	cin >> n >> m >> source >> dest;

	rep(i,1,m+1) {
		ll l,r;cin>> l >> r;
		ll a,b;cin>> a>> b;		// a is the time and b is the multiples value
		v[l].pb({r,{a,b}});
		v[r].pb({l,{a,b}});
	}

	dijkstra(source,dest);
	/*rep(i,1,n+1) {
		test2(i,dist[i]);
	}
	test1(vis[dest]);*/
	if( vis[dest])
		cout << dist[dest] << endl;
	else
		cout << -1 << endl;
}

	