//限制行走时间的最短路

//POJ1613-ZOJ1791

//Time:16Ms	Memory:324K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX	505

#define MAXT 55

#define MAXS MAXT*3

#define INF 0x3f3f3f3f

struct Edge {

	int u, v, w;

	int t[MAXT], lt;	//lt:开启与关闭时间点总和

}e[MAX];

int n, m, s, t;

int d[MAXT];

void bellman_ford()

{

	memset(d, 0x3f, sizeof(d));

	d[s] = 0;

	for (int i = 1; i <= n; i++)

		for (int j = 0; j < m; j++)

			for (int k = 1; k <= e[j].lt; k += 2)

			{

				int u = e[j].u, v = e[j].v;

				//tu:从u出发到v的时间

				int tu = max(d[u], e[j].t[k - 1]) + e[j].w;

				int tv = max(d[v], e[j].t[k - 1]) + e[j].w;

				if (tu <= e[j].t[k] || tv <= e[j].t[k])	//几次WA是因为没有取'='

				{

					if (tv <= e[j].t[k]) d[u] = min(d[u], tv);

					if (tu <= e[j].t[k]) d[v] = min(d[v], tu);

					break;

				}

			}

}

int main()

{

	char str[MAXS];

	while (scanf("%d", &n), n)

	{

		memset(e, 0, sizeof(e));

		scanf("%d%d%d", &m, &s, &t);

		for (int i = 0; i < m; i++)

		{

			scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

			e[i].lt = 1;

			cin.getline(str, MAXS);

			int len = strlen(str);

			for (int j = 0; j < len; j++)

			{

				bool flag = false;	//有无数值

				while (str[j] >= '0' && str[j] <= '9')

				{

					e[i].t[e[i].lt] = e[i].t[e[i].lt] * 10 + str[j++] - '0';

					flag = true;	//已记录数值

				}

				if (flag)	e[i].lt++;

			}

			e[i].t[e[i].lt] = INF;	//偶数时当做+∞，奇数时无用

		}

		bellman_ford();

		if (d[t] == INF) printf("*\n");

		else	printf("%d\n", d[t]);

	}

	return 0;

}