#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define int long long
const int N = 1e5+10;
struct node{
	int t;
	int k;
};
map<int,node> mp;
bool vis[N];
vector<pair<int,pair<int,int>>> adj[N];
int dist[N];
void solve()
{
	int n,m,x,y;
	cin >> n >> m >> x >> y;
	for(int i= 0;i < m;i++)
	{
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		adj[a].pb({b,{c,d}});
		adj[b].pb({a,{c,d}});
	}
	for(int i = 0;i <=n;i++)
		dist[i]=1e17;
	dist[x] = 0;
	priority_queue<pair<int,int>> q;
	q.push({0,x});
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u] = true;
		for(auto x : adj[u])
		{
			int v = x.first;
			int t = x.second.first;
			int k=x.second.second;
			int new_dist = ((dist[u] + k-1) / k) * k + t;
			if(dist[v] > new_dist){
				dist[v] = new_dist;
				q.push({-dist[v], v});
			}
		}
	}
	cout << (dist[y]==1e17?-1:dist[y]);
}
 
int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
   	//cin >> t;
    while(t--)
    {
        solve(); 
    }
}
#include<iostream>
#include<map>
#include<set>
using namespace std;
map<char,int> mp;
string a[3];
long long p[3],k;
set<char> s;
char c[10];
bool b[10],en;
void dfs(int t)
{
	if(en)
	return;
	if(t==k)
	{
		if(mp[a[0][0]]&&mp[a[1][0]]&&mp[a[2][0]])
		{
			for(int i=0;i<3;++i)
			{
				p[i]=0;
				for(int j=0;j<a[i].size();++j)
				p[i]=p[i]*10+mp[a[i][j]];
			}
			if(p[0]+p[1]==p[2])
			{
				en=1;
				cout<<p[0]<<endl<<p[1]<<endl<<p[2]<<endl;
			}
		}
		return;
	}
	for(int i=0;i<10;++i)
	{
		if(!b[i])
		b[i]=1,mp[c[t]]=i,dfs(t+1),b[i]=0;
	}
}
int main()
{
	cin>>a[0]>>a[1]>>a[2];
	for(int i=0;i<3;++i)
	for(int j=0;j<a[i].size();++j)
	s.insert(a[i][j]);
	k=s.size();
	if(k>10)
	{
		cout<<"UNSOLVABLE\n";
		return 0;
	}
	for(int i=0;i<k;++i)
	c[i]=*s.begin(),s.erase(s.begin());
	dfs(0);
	if(!en)
	cout<<"UNSOLVABLE\n";
	return 0;
}