include[HTML_REMOVED]
using namespace std;
const int N=1e6+10,INF=1e9;
typedef pair[HTML_REMOVED]pii;
struct edge
{
int v;
int w;
};
vector[HTML_REMOVED]e[N];
int d1[N],d2[N],num[N],st[N];
int n,m;
void dijkstra(int s,int d[],int idx)
{
for(int i=0;i<=n;i)
{
d[i]=INF;
st[i]=false;
}
d[s]=0;
priority_queue[HTML_REMOVED]q;
q.push({0,s});
while(q.size())
{
int u=q.top().second;
q.pop();
if(!st[u])
{
st[u]=true;
for(auto ed:e[u])
{
int v=ed.v;
int w=ed.w;
if(num[v]!=idx)
{
continue;
}
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push({-d[v],v});
}
}
}
}
}
int main()
{
while(cin>>n,n)
{
cin>>m;
while(m–)
{
int a,b,c;
cin>>a>>b>>c;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
for(int i=1;i<=n;i)
{
cin>>num[i];
}
dijkstra(1,d1,1);
// for(int i=1;i<=n;i)
// {
// cout<<”xx:”<<d1[i]<<endl;
// }
dijkstra(2,d2,2);
int ans=INF;
for(int i=1;i<=n;i)
{
for(auto ed:e[i])
{
int v=ed.v;
int w=ed.w;
if(num[i]==1&&num[v]==2)
{
ans=min(ans,d1[i]+d2[v]+w);
}
}
}
if(ans!=INF)
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
for(int i=1;i<=n;i++)
{
e[i].clear();
}
}
}