88pts玄关求调（调一晚上了看看蒟蒻吧

4 4
1 4 2 3
1 2 1
1 3 1
2 4 1
3 4 1

1

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

6

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1510, M = 600010;

typedef long long LL;

int n, m;
LL g[N][N];
LL d[5][N];
int h[N], e[M], w[M], ne[M], idx;
LL f[N]; int din[N], q[N], hh = 1, tt;
int s[5]; bool st[N];

void add(int a, int b, int c) {
    e[ ++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

void dijkstra(LL d[], int srt) {
    memset(st, 0, sizeof st);
    for (int i = 1; i <= n; i ++ ) d[i] = 1e11;
    d[srt] = 0;
    for (int k = 1; k <= n; k ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ )
            d[j] = min(d[j], d[t] + g[t][j]);
    }
}

void topsort() {
    for (int i = 1; i <= n; i ++ ) if (!din[i]) q[ ++ tt] = i;
    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; i; i = ne[i]) {
            int j = e[i];
            if ( -- din[j] == 0) q[ ++ tt] = j;
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < 4; i ++ ) cin >> s[i];
    memset(g, 0x3f, sizeof g);
    while (m -- ) {
        int a, b; LL c; cin >> a >> b >> c; g[a][b] = g[b][a] = min(g[a][b], c);
    }
    for (int i = 0; i < 4; i ++ ) dijkstra(d[i], s[i]);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            if (g[i][j] < g[0][0]) {
                int x = (d[2][i] < d[2][j] ? i : j), y = (d[2][i] < d[2][j] ? j : i);
                if (d[2][x] + g[i][j] + d[3][y] != d[2][s[3]]) continue;
                x = (d[0][i] < d[0][j] ? i : j), y = (d[0][i] < d[0][j] ? j : i);
                if (d[0][x] + g[i][j] + d[1][y] != d[0][s[1]]) continue;
                add(x, y, g[i][j]), din[y] ++ ; 
            }
    topsort();
    for (int i = 1; i <= n; i ++ )
        for (int j = h[q[i]]; j; j = ne[j]) {
            int k = e[j];
            f[k] = max(f[k], f[q[i]] + w[j]);
        }
    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}