Royal Parade

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
typedef long long int ll;
struct edge{
    int v;
    ll w;
    bool operator < (const edge& rhs)const
    {
        return w > rhs.w;
    }
};

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    vector<edge> adj[n+1];
    for(int i = 0 ; i < m ; i ++){
        int u,v;
        ll w;
        scanf("%d %d %lld",&u,&v,&w);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    int a,b;
    scanf("%d %d",&a,&b);
    ll distA[n+1];
    ll distB[n+1];
    ll distC[n+1];
    bool visitedA[n+1];
    bool visitedB[n+1];
    bool visitedC[n+1];
    bool check[n+1];
    for(int i = 0 ; i <= n ; i ++){
        distA[i] = 1e18;
        distB[i] = 1e18;
        distC[i] = 1e18;
        visitedA[i] = false;
        visitedB[i] = false;
        visitedC[i] = false;
        check[i] = true;
    }
    priority_queue<edge> pq;
    distA[a] = 0;
    pq.push({a,distA[a]});

    while(!pq.empty()){
        int u = pq.top().v;
        pq.pop();
        if(visitedA[u])continue;
        visitedA[u] = true;

        for(int i = 0 ; i < adj[u].size() ; i ++){
            int v = adj[u][i].v;
            ll w = adj[u][i].w;
            if(!visitedA[v] && distA[u] + w < distA[v]){
                distA[v] = distA[u] + w;
                pq.push({v,distA[v]});
            }
        }
    }
/*  printf("distA : ");
    for(int i = 1 ; i <= n ; i ++){
        printf("%lld ",distA[i]);
    }
    printf("\n");*/


    distB[b] = 0;
    pq.push({b,distB[b]});
    while(!pq.empty()){
        int u = pq.top().v;
        pq.pop();
    //  printf("Test dijstraB u #%d\n",u);
        if(visitedB[u])continue;
        visitedB[u] = true;

        for(int i = 0 ; i < adj[u].size() ; i ++){
            int v = adj[u][i].v;
            ll w = adj[u][i].w;
            if(!visitedB[v] && distB[u] + w < distB[v]){
                distB[v] = distB[u] + w;
                pq.push({v,distB[v]});
            }
        }
    }

/*  printf("distB : ");
    for(int i = 1 ; i <= n ; i ++){
        printf("%lld ",distB[i]);
    }
    printf("\n");*/

    for(int i = 1 ; i <= n ; i ++){
        if(distA[i] + distB[i] == distA[b]){
            check[i] = false;
    //      printf("Test checked %d\n",i);
        }
    }
    int c,d;
    scanf("%d %d",&c,&d);

    distC[c] = 0;
    pq.push({c,distC[c]});
    while(!pq.empty()){
        int u = pq.top().v;
        pq.pop();
        if(visitedC[u] || !check[u])continue;
        visitedC[u] = true;

        for(int i = 0 ; i < adj[u].size() ; i ++){
            int v = adj[u][i].v;
            ll w = adj[u][i].w;
            if(check[v] && !visitedC[v] && distC[u] + w < distC[v]){
                distC[v] = distC[u] + w;
                pq.push({v,distC[v]});
            }
        }
    }
    printf("%lld",(distC[d] == 1e18 ? -1 : distC[d]));
    return 0;
}