#include "stdio.h"
#include "string.h"
#include "limits.h"

struct ttun
{
	int u, v, c, nlst;
	int lst[35];
} tun[500];
int n, m, src, tag;

int getcost(int start, int cho)
{
	if (tun[cho].nlst == 0 || start + tun[cho].c <= tun[cho].lst[0])
		return start + tun[cho].c;
	for (int i = 1; i < tun[cho].nlst; i += 2)
	{
		int sta = start > tun[cho].lst[i] ? start : tun[cho].lst[i];
		if (i == tun[cho].nlst - 1 || sta + tun[cho].c <= tun[cho].lst[i + 1])
		{
			return sta + tun[cho].c;
		}
	}
	return INT_MAX;
}

int dijkstra()
{ int i, j, k;
  int D[50], used[50];

	for (i = 0; i < n; i ++)
	{
		D[i] = INT_MAX;
		used[i] = 0;
	}
	D[src] = 0;

	for (i = 0; i < n; i ++)
	{
		int min = INT_MAX;
		for (j = 0; j < n; j ++)
			if (!used[j] && D[j] < min)
			{
				min = D[j];
				k = j;
			}
		if (min == INT_MAX || k == tag) break;
		used[k] = 1;
		for (j = 0; j < m; j ++)
		{
			if (tun[j].u == k || tun[j].v == k)
			{
				int p = tun[j].u + tun[j].v - k;
				if (used[p]) continue;
				int cost = getcost(D[k], j);
				if (cost < D[p])
					D[p] = cost;
			}
		}
	}
	return D[tag];
}

int getnum(char *inf, int &p, int len)
{ int ans = 0;
	while (p < len && (inf[p] < '0' || inf[p] > '9')) p ++;
	while (p < len && inf[p] >= '0' && inf[p] <= '9')
	{
		ans = ans * 10 + int(inf[p++]) - 48;
	}
	return ans;
}

int main()
{ int i;
  char inf[1000];

//	freopen("in.txt", "r", stdin);

	while (scanf("%d", &n), n > 0)
	{
		for (i = 0; i < n; i ++)
			memset(&tun[i], 0, sizeof(tun[i]));

		scanf("%d%d%d", &m, &src, &tag);
		src --;
		tag --;

		for (i = 0; i < m; i ++)
		{
			scanf("%d%d%d", &tun[i].u, &tun[i].v, &tun[i].c);
			tun[i].u --;
			tun[i].v --;
			gets(inf);
			int p = 0;
			int len = strlen(inf);
			while (p < len)
			{
				tun[i].lst[tun[i].nlst++] = getnum(inf, p, len);
			}
		}

		int ans = dijkstra();

		if (ans == INT_MAX)
			printf("*\n");
		else
			printf("%d\n", ans);
	}
	return 0;
}