#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vlll = vector<vll>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define co(i) cout << i << endl;
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.second < secondElof.second;
}
//AtCoder以外ではコメントアウトを忘れずに！
//#include <atcoder/all>
//using namespace atcoder;
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod, LIS, digitDP, treeDP, Rerooting//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal, RMQ, LCA, FordFulkerson//
//**AC Libraryリスト**//
//pow_mod, inv_mod, floor_sum, convolution, convolution_ll, modint//
//fenwicktree, segtree, lazysegtree, string//
ll i, j, k, l; ll N, M, K, H, W, X, Y, Z, R, Q;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vector<vtll> path;
//***********//
map<ll, ll> flag;
vll path2;
vl T;
void dijkstra(ll s) {
	priority_queue<pll> PQ;
	vl D(N+M), color(N+M);
	for (ll i = 0; i < N+M; i++) {
		D[i] = INF;
		color[i] = 0;
	}
	D[s] = 0;
	//PQ.push(make_pair(0, s));
	color[s] = 1;
	ll q = -1;
	//debug(path2[s]);
	for (ll i = 0; i < path2[s].size(); i++) {
		D[N + path2[s][i]] = 0;
		PQ.push(make_pair(0, N+path2[s][i]));
	}
	while (!PQ.empty()) {
		pll f = PQ.top();
		PQ.pop();
		ll u = f.second;
		//debug(u);
		color[u] = 2;
		if (D[u] < f.first * q) {
			continue;
		}
		for (ll j = 0; j < path[u].size(); j++) {
			ll v = get<0>(path[u][j]);
			//debug(v);
			//debug(path2[v]);
			if (color[v] == 2) {
				continue;
			}
			if (D[v] > D[u] + get<1>(path[u][j])) {
				D[v] = D[u] + get<1>(path[u][j]);
				color[v] = 1;
				//PQ.push(make_pair(D[v] * q, v));
				for (ll k = 0; k < path2[v].size(); k++) {
					ll m = path2[v][k];
					ll pre = D[v];
					if (D[v] % T[m] != 0) {
						pre += T[m] - D[v] % T[m];
					}
					if (D[N + m] > pre) {
						D[N + m] = pre;
						color[N + m] = 1;
						PQ.push(make_pair(D[N + m] * q, N + m));
					}
				}
			}
		}
	}
	//debug(D);
	if (D[Y] == INF) cout << -1;
	else cout << D[Y];
}
int main() {
	cin >> N >> M >> X >> Y;
	//N+1~N*(M+1)まで
	map<ll,ll> flag;
	T.resize(M);
	path.resize(N + M);
	path2.resize(N);
	for (i = 0; i < M; i++) {
		ll a, b, t, k;
		cin >> a >> b >>t >> k;
		T[i] = k;
		a--; b--;
		path[N+i].push_back(mt(b, t,k));
		path[N + i].push_back(mt(a, t, k));
		path2[a].push_back(i);
		path2[b].push_back(i);
	}
	X--; Y--;
	dijkstra(X);
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=2e5+5,Mod=998244353;
int quick_pow(int a,int k){
	int ans=1;
	while(k){
		if(k&1)ans=1LL*ans*a%Mod;
		a=1LL*a*a%Mod;
		k>>=1;
	}
	return ans;
}
int main()
{
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	int n=read_int(),m=read_int(),k=read_int();
	if(n==1||m==1)
	enter(quick_pow(k,n+m-1));
	else{
		int ans=0;
		_rep(i,1,k)
		ans=(ans+1LL*(quick_pow(i,n)-quick_pow(i-1,n)+Mod)*quick_pow(k-i+1,m))%Mod;
		enter(ans);
	}
	return 0;
}