#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2000;
struct ok{
ll v,w,c;
};
vector<ok> g[N+5];
struct ok1{
ll u,kc,x,ma1, ma2;
};
 
struct cmp{
bool operator() (ok1 &a , ok1 &b){
 return a.kc>b.kc;
 }
};
ll d[N+5][N+5];
 
void siu(ll s){
for(int i=0;i<=N;i++)
       for(int j=0;j<=N;j++)
        d[i][j]=1e16;
 
 priority_queue<ok1, vector<ok1> , cmp> q;
 d[s][0]=0;
q.push({s,0,0,0,0});
 
while(!q.empty()){
 ok1 x1=q.top();
 q.pop();
 ll u=x1.u, kc=x1.kc, x=x1.x, ma1=x1.ma1, ma2=x1.ma2;
 
   if(kc != d[u][x]) continue;
    for(auto v1:g[u]){
        ll v=v1.v, w=v1.w , c=v1.c;
        if(c==2){
                ll ma=max(ma2,w);
 
             if(d[v][x+1] > ma+ma1){
                d[v][x+1]= ma+ma1;
         q.push({v,d[v][x+1],x+1,ma1,ma}); }
        }
        else{
                ll ma=max(ma1,w);
              if(d[v][x] > ma+ma2){
                d[v][x]=ma+ma2;
 
         q.push({v,d[v][x],x,ma,ma2}); }
        }
    }
  }
}
int main(){
    ll n,m,s,t;
    cin>>n>>m>>s>>t;
    ll d1=0;
 
    for(int i=1;i<=m;i++){
        ll c,u,v,w;
        cin>>c>>u>>v>>w;
        if(c==2) d1++;
        g[u].push_back({v,w,c});
        g[v].push_back({u,w,c});
    }
 
siu(s);
 ll res=1e16;
 for(int i=0;i<=d1;i++)
    res=min(res,d[t][i]);
 cout<<res;
    return 0;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgbGwgTj0yMDAwOwpzdHJ1Y3Qgb2t7CmxsIHYsdyxjOwp9Owp2ZWN0b3I8b2s+IGdbTis1XTsKc3RydWN0IG9rMXsKbGwgdSxrYyx4LG1hMSwgbWEyOwp9OwoKc3RydWN0IGNtcHsKYm9vbCBvcGVyYXRvcigpIChvazEgJmEgLCBvazEgJmIpewogcmV0dXJuIGEua2M+Yi5rYzsKIH0KfTsKbGwgZFtOKzVdW04rNV07Cgp2b2lkIHNpdShsbCBzKXsKZm9yKGludCBpPTA7aTw9TjtpKyspCiAgICAgICBmb3IoaW50IGo9MDtqPD1OO2orKykKICAgICAgICBkW2ldW2pdPTFlMTY7CgogcHJpb3JpdHlfcXVldWU8b2sxLCB2ZWN0b3I8b2sxPiAsIGNtcD4gcTsKIGRbc11bMF09MDsKcS5wdXNoKHtzLDAsMCwwLDB9KTsKCndoaWxlKCFxLmVtcHR5KCkpewogb2sxIHgxPXEudG9wKCk7CiBxLnBvcCgpOwogbGwgdT14MS51LCBrYz14MS5rYywgeD14MS54LCBtYTE9eDEubWExLCBtYTI9eDEubWEyOwoKICAgaWYoa2MgIT0gZFt1XVt4XSkgY29udGludWU7CiAgICBmb3IoYXV0byB2MTpnW3VdKXsKICAgICAgICBsbCB2PXYxLnYsIHc9djEudyAsIGM9djEuYzsKICAgICAgICBpZihjPT0yKXsKICAgICAgICAgICAgICAgIGxsIG1hPW1heChtYTIsdyk7CgogICAgICAgICAgICAgaWYoZFt2XVt4KzFdID4gbWErbWExKXsKICAgICAgICAgICAgICAgIGRbdl1beCsxXT0gbWErbWExOwogICAgICAgICBxLnB1c2goe3YsZFt2XVt4KzFdLHgrMSxtYTEsbWF9KTsgfQogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgbGwgbWE9bWF4KG1hMSx3KTsKICAgICAgICAgICAgICBpZihkW3ZdW3hdID4gbWErbWEyKXsKICAgICAgICAgICAgICAgIGRbdl1beF09bWErbWEyOwoKICAgICAgICAgcS5wdXNoKHt2LGRbdl1beF0seCxtYSxtYTJ9KTsgfQogICAgICAgIH0KICAgIH0KICB9Cn0KaW50IG1haW4oKXsKICAgIGxsIG4sbSxzLHQ7CiAgICBjaW4+Pm4+Pm0+PnM+PnQ7CiAgICBsbCBkMT0wOwoKICAgIGZvcihpbnQgaT0xO2k8PW07aSsrKXsKICAgICAgICBsbCBjLHUsdix3OwogICAgICAgIGNpbj4+Yz4+dT4+dj4+dzsKICAgICAgICBpZihjPT0yKSBkMSsrOwogICAgICAgIGdbdV0ucHVzaF9iYWNrKHt2LHcsY30pOwogICAgICAgIGdbdl0ucHVzaF9iYWNrKHt1LHcsY30pOwogICAgfQoKc2l1KHMpOwogbGwgcmVzPTFlMTY7CiBmb3IoaW50IGk9MDtpPD1kMTtpKyspCiAgICByZXM9bWluKHJlcyxkW3RdW2ldKTsKIGNvdXQ8PHJlczsKICAgIHJldHVybiAwOwp9Cg==

NiA3IDEgNAoxIDEgMiA0CjIgMiAzIDcKMSAzIDQgNgoyIDEgNiA1CjEgNiA1IDUKMiA1IDQgOAoyIDIgNSAyCg==

6 7 1 4
1 1 2 4
2 2 3 7
1 3 4 6
2 1 6 5
1 6 5 5
2 5 4 8
2 2 5 2