#include <bits/stdc++.h>
#define ss second
#define ll long long 
#define mod 1000000007
#define ff first
#define pb push_back
#define pll pair<ll,ll>
#define w(x) ll x; cin>>x; while(x--)
#define ps(x,y) fixed<<setprecision(y)<<x;
#define fo(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define re(i, j) fo(i, 0, j, 1)
#define pi acos(-1)
#define all(cont) cont.begin(), cont.end()
#define countbit(x) __builtin_popcount(x)
#define de(n) ll n;cin>>n;
#define def(a,n) ll n;cin>>n;ll a[n];re(i,n){cin>>a[i];}
#define defi(a,n,k) ll n;cin>>n; ll k;cin>>k;ll a[n];re(i,n){cin>>a[i];}
#define deb(x) cout<<#x<<"="<<x<<endl;
#define tr(it,a) for(auto it=a.begin();it!=a.end();it++)
#define nl cout<<endl;
using namespace std;
//18-1326D1 1208B 845C 912B 1009B 1350C 20C 1333C 1234D 1327C 1305B 1304B (or in matrix) 1216-C(26) 21
void cp()
{
    ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    #ifndef ONLINE_JUDGE  
    freopen("input.txt", "r", stdin);  
    freopen("output.txt", "w", stdout);
#endif
}
ll powermod(ll x, ll y,ll p)  
{  
    int res = 1;
    x = x % p; 
    if (x == 0) return 0;
    while (y > 0)  
    {   
        if (y & 1)  
            res = (res*x) % p;  
   
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}
int main()
{
    //cp();
	de(n);
	de(p);
	if(p==2)
	{
		if(n==1)
		cout<<"1";
		else{
			cout<<"0";
		}
	}
	else
	{
		ll ans=powermod(p-2,n-1,mod);
		ans=((ans%mod)*((p-1)%mod))%mod;
		cout<<ans;
	}
}
// Problem: E - Train
// Contest: AtCoder - AtCoder Beginner Contest 192
// URL: https://atcoder.jp/contests/abc192/tasks/abc192_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define ll long long
#define mod 1000000007

// templates
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define po(x, y) fixed << setprecision(y) << x
#define ss(s) scanf(" %[^\n]%*c", s)
#define sc(n) scanf("%d", &n)
#define sl(n) scanf("%lld", &n)
#define ps(s) printf("%s\n", s)
#define pr(n) printf("%d\n", n)
#define pl(n) printf("%lld\n", n)
#define prs(n) printf("%d ", n)
#define pls(n) printf("%lld ", n)
using namespace std;

const ll inf = (ll)1e16 + 10;
const int N = (int)1e5 + 10;
int a[N], b[N];
vector<array<ll, 3>> adj[N];  // u->v,t,k
vector<ll> dist(N);
ll n, m, x, y;
void bfs() {
  set<array<ll, 2>> s;  // time,node
  s.insert({0, x});
  for (int i = 0; i <= n; i++) {
    dist[i] = inf;
  }
  dist[x] = 0;
  while (sz(s)) {
    auto temp = *s.begin();
    s.erase(s.begin());
    ll node = temp[1], kete = temp[0];
    for (auto c : adj[node]) {
      ll add = 0;
      if (kete < c[2] && kete != 0) {
        add = (c[2] - kete);
      } else if (kete != 0) {
        if (kete % c[2]) {
          add = c[2] - (kete % c[2]);
        }
      }
      ll curr = c[1] + add + kete;
      // printf("node-> %lld curr-> %lld\n", node, curr);
      if (dist[c[0]] > curr) {
        s.erase({dist[c[0]], c[0]});
        dist[c[0]] = curr;
        s.insert({curr, c[0]});
      }
    }
  }
  if (dist[y] == inf) {
    dist[y] = -1;
  }
  pl(dist[y]);
}
void solve() {
  sl(n), sl(m), sl(x), sl(y);
  for (int i = 1; i <= m; i++) {
    ll u, v, t, k;
    sl(u), sl(v), sl(t), sl(k);
    adj[u].push_back({v, t, k});
    adj[v].push_back({u, t, k});
  }
  bfs();
}

int main() {
  // #ifndef ONLINE_JUDGE
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  // #endif
  int t = 1;
  // sc(t);
  while (t--) {
    solve();
  }
  // cerr << (float)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
  return 0;
}