#include <bits/stdc++.h>
#define L(i, m, n) for(int i(m);i < n;i++)
#define pb push_back
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define in(x) cin >> x
#define SZ(X) int(X.size())
#define clr(A, V) L(i, 0, 111) A[i]=V
#define ff first
#define ss second
#define RF(X) freopen(X, "r", stdin)
#define WF(X) freopen(X, "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<int, string> pis;
typedef vector<string> vs;
typedef pair<pair<int, int>, pair<int, int > > piiii;

const int INF=1e9;
vi dist(55, INF); /**Don't forget to check nodes number and memset each test**/
vi a[55][55];
vector <vi> b;
int n,m,source,t,INDEX;
int solve(int idx, int ini){
//    D(idx);D(ini);
    int w = b[idx][0]; /** 0 2 4 6 **//**even open odd close**/
    if(SZ(b[idx])==1) return ini+w; /**no obstacles**/
    if(ini+w <= b[idx][1]) return ini+w;
    for(int i = 2;i< SZ(b[idx]);i+=2){
        if(i == SZ(b[idx])-1) return max(ini, b[idx][i])+w;
        else if(max(ini+w, b[idx][i]+w)<=b[idx][i+1])
            return max(b[idx][i]+w,ini+w);
    }
//    D(idx); D(w);D(ini);D(SZ(b[idx])-1);
    return INF;
}
void Dijkstra(int &s){
    dist[s] = 0; /** INF = 1B to avoid overflow**/
    priority_queue< pii, vpii, greater<pii> > pq; /**parameters**/
    pq.push({0, s}); /** TIME , NODE**/
    while (!pq.empty()){
        pii front = pq.top(); pq.pop(); int d=front.ff,u=front.ss;
        if(d > dist[u]) continue;
        L(j,1,n+1)
            if(SZ(a[u][j]))
                L(k, 0, SZ(a[u][j])){
                    int cost = solve(a[u][j][k], d);
//                    D(cost);D(j);D(dist[j]);
                    if(cost < dist[j]) dist[j]=cost,pq.push({cost, j});
                }

    } /** this variant can cause duplicate items in the priority queue**/
}
string s;
void init(){

    L(i,0,55)L(j,0,55) a[i][j].clear();
    b.clear();
    L(i,0,55) dist[i]=INF;
    INDEX=0;
}
int main(){
//    RF("in.txt");
//    WF("out.txt");
    int debug=0;
    while(1){
        init();
//        ++debug;
        scanf("%d",&n);if(!n)return 0;scanf("%d%d%d", &m,&source,&t);
//        if(debug == 68)
//            cout << n << " " << m << " " << source << " " << t <<endl;
        getline(cin,s);

        L(i,0,m){
            vi temp;
            getline(cin,s);
            stringstream stream(s);
//            if(debug==68)
//                cout << s<<endl;
            while(stream){
                int n;
                stream >> n;
                temp.pb(n);
            }
            temp.pop_back();//msh 3aref leh
            int x=temp[0]; int y= temp[1];
            temp.erase(temp.begin(),temp.begin()+2);
            a[x][y].pb(INDEX); a[y][x].pb(INDEX);
            b.pb(temp);INDEX++;
        }
//        if(debug != 68) continue;
        Dijkstra(source);
        if(dist[t]==INF) printf("*\n");
        else printf("%d\n",dist[t]);


    }
}