//方法1：spfa版本
Memory: 768K
Time: 32MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 605
#define INF 0x3f3f3f3f
int colour[MAXN];
int dis[MAXN];
int vis[MAXN];
int map[MAXN][MAXN];
struct node
{
    int to,w;
    node(){}
    node(int to,int w):to(to),w(w){}
};
vector<node>edges[MAXN];
void init(int n)
{
    for(int i=0;i<=n;i++)
    {
        vis[i]=0;
        colour[i]=0;
        dis[i]=INF;
        for(int j=0;j<=n;j++)
        {
            map[i][j]=0;
        }
        edges[i].clear();
    }
}
void add(int u,int v,int w)
{
    edges[u].push_back(node(v,w));
}
int spfa(int s,int t)
{
    queue<int>que;
    que.push(s);
    vis[s]=1;
    dis[s]=0;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=0;
        int len=edges[u].size();
        for(int i=0;i<len;i++)
        {
            int v=edges[u][i].to;
            int w=edges[u][i].w;
            if(dis[v]>=dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    que.push(v);
                }
            }
        }
    }
    return dis[t];
}
int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&m);
        init(n);
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a>b)swap(a,b);
            map[a][b]=c;
        }
        for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            colour[i]=a;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(map[i][j])
                {
                    if(colour[i]==colour[j])
                    {
                        add(i,j,map[i][j]);
                        add(j,i,map[i][j]);
                    }
                    else
                    {
                        if(colour[i]==colour[1])
                        {
                            add(i,j,map[i][j]);
                        }
                        else
                        {
                            add(j,i,map[i][j]);
                        }
                    }
                }
            }
        }
        int ans=spfa(1,2);
        if(ans==INF)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
    return 0;
}
//dijkstra版本
Memory:572K
Time: 16MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 605
#define INF 0x3f3f3f3f
int colour[MAXN];
int dis[MAXN];
int vis[MAXN];
int map[MAXN][MAXN];
int n,m;
void init()
{
    for(int i=0;i<=n;i++)
    {
        vis[i]=0;
        colour[i]=0;
        for(int j=0;j<=n;j++)
        {
            if(i==j)map[i][j]=0;
            else map[i][j]=INF;
        }
    }
}
int dijkstra(int s,int t)
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=map[s][i];
    }
    dis[s]=0;
    vis[s]=1;
    for(int i=1;i<n;i++)
    {
        int MIN=INF;
        int k=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<MIN)
            {
                MIN=dis[j];
                k=j;
            }
        }
        vis[k]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>dis[k]+map[k][j])
            {
                dis[j]=dis[k]+map[k][j];
            }
        }
    }
    return dis[t];
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&m);
        init();
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
        }
        for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            colour[i]=a;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(map[i][j])
                {
                    if(colour[i]!=colour[j])
                    {
                        if(colour[i]==colour[1])
                        {
                            map[j][i]=INF;
                        }
                        else
                        {
                            map[i][j]=INF;
                        }
                    }
                }
            }
        }
        int ans=dijkstra(1,2);
        if(ans==INF)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
    return 0;
}
//spfa(简单思维判断)
Memory: 320K
Time: 16MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 605
#define INF 0x3f3f3f3f
int colour[MAXN];
int dis[MAXN];
int vis[MAXN];
struct node
{
    int to,w;
    node(){}
    node(int to,int w):to(to),w(w){}
};
vector<node>edges[MAXN];
struct link
{
    int to;
    int cnt[2][2];
    link(){}
};
void init()
{
    memset(colour,0,sizeof(colour));
    for(int i=0;i<MAXN;i++)
    {
        edges[i].clear();
    }
}
void add(int u,int v,int w)
{
    edges[u].push_back(node(v,w));
    edges[v].push_back(node(u,w));
}
int spfa(int s,int t)
{
    fill(dis,dis+MAXN,INF);
    memset(vis,0,sizeof(vis));
    queue<link>que;
    link rt;
    rt.to=s;
    memset(rt.cnt,0,sizeof(rt.cnt));
    rt.cnt[colour[s]][colour[s]]++;
    que.push(rt);
    vis[s]=1;
    dis[s]=0;
    while(!que.empty())
    {
        link curr=que.front();
        que.pop();
        vis[curr.to]=0;
        int len=edges[curr.to].size();
        for(int i=0;i<len;i++)
        {
            link next=curr;
            int v=edges[curr.to][i].to;
            int w=edges[curr.to][i].w;
            next.to=v;
            next.cnt[colour[curr.to]][colour[v]]++;
            next.cnt[colour[v]][colour[curr.to]]++;
            if(colour[s]==colour[t])
            {
                if(colour[v]==colour[s])
                {
                    if(dis[v]>dis[curr.to]+w)
                    {
                        dis[v]=dis[curr.to]+w;
                        if(!vis[v])
                        {
                            vis[v]=1;
                            que.push(next);
                        }
                    }
                }
            }
            else
            {
                if(next.cnt[colour[s]][colour[t]]<=1&&next.cnt[colour[t]][colour[s]]<=1)
                {
                    if(dis[v]>dis[curr.to]+w)
                    {
                        dis[v]=dis[curr.to]+w;
                        if(!vis[v])
                        {
                            vis[v]=1;
                            que.push(next);
                        }
                    }
                }
            }
        }
    }
    return dis[t];
}
int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&m);
        init();
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            colour[i]=a-1;
        }
        int ans=spfa(1,2);
        if(ans==INF)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
    return 0;
}