BUS 70%

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 50005;

typedef pair<ll, ll> ii;

struct pt {
    ll u, v, w;
};

ll n, m, s, t;
vector<pt> a[N];

pt A[N], B[N];
ll nB, nA;
bool kt = false;
ll d[3][N], parent[N];

void Dijkstra(ll s, ll q) {
    priority_queue<ii, vector<ii>, greater<ii> >pq;

    for(int i = 1; i <= n; i++)
        d[q][i] = 1e18;
    d[q][s] = 0;
    pq.push({0, s});

    while(pq.size()) {
        ll u = pq.top().second;
        ll du = pq.top().first;
        pq.pop();

        if(du != d[q][u]) continue;

        for(int i = 0; i < a[u].size();i++) {
            ll v = a[u][i].u;
            ll uv = a[u][i].w;

            if(max(du , uv) < d[q][v]) {
                d[q][v] = max(du, uv);
                pq.push({d[q][v], v});
            }
        }
    }
}

bool comp(pt a, pt b) {
    return a.w < b.w;
}

ll get_parent(ll u) {
    if (parent[u] == 0)
        return u;
    return parent[u] = get_parent(parent[u]);
}

bool join(ll u, ll v) {
    ll x = get_parent(u);
    ll y = get_parent(v);

    if (x == y) return 0;
    parent[x] = y;
    return 1;
}

ll Sub13(){
    Dijkstra(s, 0);
    //Sub1
    if(!kt) return d[0][t];

    //Sub3
    ll ans = d[0][t];
    Dijkstra(t, 1);
    for(int i = 1; i <= nB; i++){
        ll x = min(
            max(d[0][B[i].u], d[1][B[i].v]),
            max(d[0][B[i].v], d[1][B[i].u])
        );

        ans = min(ans, x + B[i].w);
    }
    return ans;
}

ll Sub2(){
    sort(B + 1, B + nB + 1, comp);
    sort(A + 1, A + nA + 1, comp);
    ll ans = 1e18;

    for(int k = 1; k <= nA; k++) {
        memset(parent, 0, sizeof(parent));

        for(int i = 1; i <= k; i++)
            join(A[i].u, A[i].v);

        for(int j = 1; j <= nB; j++) {
            join(B[j].u, B[j].v);

            if(get_parent(s) == get_parent(t)){
                ans = min(ans, B[j].w + A[k].w);
                break;
            }
        }
    }

    return ans;
}

int main() {
    //freopen("in.txt", "r", stdin);
    freopen("BUS.inp", "r", stdin);
    freopen("BUS.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++) {
        ll k, u, v, w;
        cin >> k >> u >> v >> w;

        if(k == 1) {
            a[u].push_back({v, k, w});
            a[v].push_back({u, k, w});
        }

        if(k == 2)
            B[++nB] = {u, v, w};
        else
            A[++nA] = {u, v, w};

        if(k == 2) kt = true;
    }

    if(m <= 5000) cout << Sub2();
    else cout << Sub13();
}