（2つの状態が最も短絡）nubj 2473

#include 

using namespace std;

#define pb push_back

#define Pii  pair  // first dis ,second u

const int N = 2E5 + 7;
vectorG[N];
bool a[N], vis[N];
int n, m;
int dis[N];

void add(int u, int v, int w, bool sta) //    u  ，   u        ,    
{
    if(sta) {
        G[u].pb(Pii(2 * w, n + v)); //u->v     2c  ,     v     
        G[u + n].pb(Pii(2 * w, n + v)); //       u  
    } else {
        G[u].pb(Pii(w, v)); //    
        G[u + n].pb(Pii(2 * w, v)); //   u        ，         v 
    }
}

void dij()
{
    priority_queue, greater > que;
    que.push(Pii(0,0));
    while(!que.empty()) {
        int u = que.top().second;
        que.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = 0;i < G[u].size();i ++) {
            Pii t = G[u][i];
            if(!vis[t.second] && dis[t.second] > t.first + dis[u]) {
                dis[t.second] = t.first + dis[u];
                que.push(Pii(dis[t.second], t.second));
            }
        }
    }
}
int main()
{

    scanf("%d %d", &n, &m);

    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0;
    dis[n] = 0;
    for(int i = 0;i < n;i ++) scanf("%d", &a[i]);
    for(int i = 1;i <= m;i ++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w, a[u]);
        add(v, u, w, a[v]);
    }
    dij();
    printf("%d
", min(dis[n-1], dis[2*n-1]));
    return 0;
}