TLE on #6, 7, 8, 10

// Problem: P2149 [SDOI2009]Elaxia的路线
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2149
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define fastIO ios :: sync_with_stdio(0)
const int maxn = 3000500;

inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}

int n, m;
int x_1, y_1, x_2, y_2;
int dis[5][maxn], ind[maxn], ans[maxn];
int st[maxn], top;
struct edge
{
    int tot, head[maxn], ver[maxn], val[maxn], nxt[maxn], from[maxn];
    bool is_in[maxn];
}g[3];

void add(int k, int u, int v, int w, bool in)
{
    g[k].tot++;
    g[k].from[g[k].tot] = u;
    g[k].ver[g[k].tot] = v;
    g[k].val[g[k].tot] = w;
    g[k].nxt[g[k].tot] = g[k].head[u];
    g[k].head[u] = g[k].tot;
    g[k].is_in[g[k].tot] = in;
}

void spfa(int k, int s)
{
    bool vis[1555] = {};
    top = 0;
    dis[k][s] = 0;
    st[++top] = s;
    vis[s] = true;
    while(top)
    {
        int t = st[top--];
        vis[t] = false;
        for(int i=g[1].head[t]; i; i=g[1].nxt[i])
        {
            int v = g[1].ver[i], w = g[1].val[i];
            if(dis[k][v] > dis[k][t] + w)
            {
                dis[k][v] = dis[k][t] + w;
                if(!vis[v])
                {
                    st[++top] = v;
                    vis[v] = true;
                }
            }
        }
    }
}

void topo()
{
    top = 0;
    st[++top] = x_1;
    ans[x_1] = 0;
    while(top)
    {
        int t = st[top--];
        for(int i=g[2].head[t]; i; i=g[2].nxt[i])
        {
            int v = g[2].ver[i], w = g[2].val[i];
            ind[v]--;
            if(!ind[v])
                st[++top] = v;
            ans[v] = max(ans[v], ans[t] + w*g[2].is_in[i]);
        }
    }
}

int main()
{
    // fastIO;
    memset(dis, 0x3f, sizeof(dis));
    // cin >> n >> m >> x_1 >> y_1 >> x_2 >> y_2;
    n = read(), m = read();
    x_1 = read(); y_1 = read(); x_2 = read(); y_2 = read();
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        u = read(); v = read(); w = read();
        add(1, u, v, w, false);
        add(1, v, u, w, false);
    }
    spfa(1, x_1);
    spfa(2, y_1);
    spfa(3, x_2);
    spfa(4, y_2);
    for(int i=1; i<=g[1].tot; i++)
    {
        if(dis[1][g[1].from[i]] + g[1].val[i] + dis[2][g[1].ver[i]] == dis[1][y_1])
        {
            if(dis[3][g[1].from[i]] + g[1].val[i] + dis[4][g[1].ver[i]] == dis[3][y_2]
                || dis[4][g[1].from[i]] + g[1].val[i] + dis[3][g[1].ver[i]] == dis[3][y_2])
                    add(2, g[1].from[i], g[1].ver[i], g[1].val[i], true);
            else
                add(2, g[1].from[i], g[1].ver[i], g[1].val[i], false);
            ind[g[1].ver[i]]++;
        }
    }
    topo();
    // cout << ans[y_1] << endl;
    printf("%d\n", ans[y_1]);
    return 0;
}