#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
#define inf 0x3f3f3f3f
using namespace std;
const int M=10005;
struct sss
{
ll v; //终点
ll w; //边的权值
ll next;
}a[10005];
ll head[M]; //head存储的是以i为起点,最后输入的那个编号
ll vis[M],ven[M],nums[M]; //SPFS数组,vis记录最短路,ven记录是否在队列,nums记录入队次数
ll cnt=0; //链式前向星数组
void add(ll u,ll v,ll w)//链式前向星,加入节点
{
a[cnt].v=v;
a[cnt].w=w;
a[cnt].next=head[u];
head[u]=cnt++;
}
bool SPFA(int s,ll n) //从s点开始出发,一共n条边
{
queue <ll> q;
vis[s]=0; //初始化距离
ven[s]=1; //标记s在队列里面
nums[s]++;//队列次数+1
q.push(s);
while(!q.empty())
{
ll x=q.front(); //以x点为翘板
q.pop(); //出队
ven[x]=0; //标记不在队列
for(ll i=head[x]; i>=0; i=a[i].next) //遍历与x节点连通的点
{
ll y=a[i].v; //y是这条边的终点,以x为翘板,看初始点距离y点的距离可不可以更新
if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > (初始点距离x的距离+i这条边的权值) ——> 更新
{
vis[y] = vis[x] + a[i].w;
if(ven[y]==0) //由于更新了节点,所以后续以这个为基础的最短路,也要更新下,所以如果在队列就不用加入,不在的话加入更新后续节点
{
q.push(y);
ven[y]=1;//标记这个节点在队列中
nums[y]++;//记录加入次数
if(nums[y]>n) return false; //如果这个点加入超过n次,说明存在负圈,直接返回
}
}
}
}
return true;
}
ll value[1005];
void init()
{
cnt=0;
memset(vis,inf,sizeof(vis)); //设s点到其余各个点的距离都是最大值
memset(head,-1,sizeof(head)); //链式向前星里面的head数组初始化为-1
memset(nums,0,sizeof(nums));
}
int main()
{
ll n,m;
while(cin >> m >> n) //m为初始的点的个数,n为边数
{
init();
for (ll i=1;i<=m;i++)
{
cin >> value[i];
}
for(ll i=0;i<n;i++)
{
ll x,y,k;
cin >> x >> y >> k;
add(x, y, k);
add(y, x, k); //添加双向边
}
ll ans=0;
/*以哪个点为初始点、一共有多少条边*/
bool flag=SPFA(1,n);
for (ll i=2;i<=m;i++)
{
if(vis[i]>=inf)
{
flag=false;
break;
}
ans=ans+vis[i]*value[i];
}
if(flag) cout << ans << endl;
else cout << "No Answer" << endl;
}
return 0;
}
//(把ven数组删掉了,直接用nums数组储存)
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
#define inf 0x3f3f3f3f
using namespace std;
const int M=10005;
struct sss
{
ll v; //终点
ll w; //边的权值
ll next;
}a[10005];
ll head[M]; //head存储的是以i为起点,最后输入的那个编号
ll vis[M],nums[M]; //SPFS数组,vis记录最短路,ven记录是否在队列,nums记录入队次数
ll cnt=0; //链式前向星数组
void add(ll u,ll v,ll w)//链式前向星,加入节点
{
a[cnt].v=v;
a[cnt].w=w;
a[cnt].next=head[u];
head[u]=cnt++;
}
bool SPFA(int s,ll n) //从s点开始出发,一共n条边
{
queue <ll> q;
vis[s]=0; //初始化距离
nums[s]++;//队列次数+1
q.push(s);
while(!q.empty())
{
ll x=q.front(); //以x点为翘板
q.pop(); //出队
nums[x]=0; //标记不在队列
for(ll i=head[x]; i>=0; i=a[i].next) //遍历与x节点连通的点
{
ll y=a[i].v; //y是这条边的终点,以x为翘板,看初始点距离y点的距离可不可以更新
if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > (初始点距离x的距离+i这条边的权值) ——> 更新
{
vis[y] = vis[x] + a[i].w;
if(nums[y]==0) //由于更新了节点,所以后续以这个为基础的最短路,也要更新下,所以如果在队列就不用加入,不在的话加入更新后续节点
{
q.push(y);
nums[y]++;//记录加入次数
if(nums[y]>n) return false; //如果这个点加入超过n次,说明存在负圈,直接返回
}
}
}
}
return true;
}
ll value[1005];
void init()
{
cnt=0;
memset(vis,inf,sizeof(vis)); //设s点到其余各个点的距离都是最大值
memset(head,-1,sizeof(head)); //链式向前星里面的head数组初始化为-1
memset(nums,0,sizeof(nums));
}
int main()
{
ll n,m;
while(cin >> m >> n) //m为初始的点的个数,n为边数
{
init();
for (ll i=1;i<=m;i++)
{
cin >> value[i];
}
for(ll i=0;i<n;i++)
{
ll x,y,k;
cin >> x >> y >> k;
add(x, y, k);
add(y, x, k); //添加双向边
}
ll ans=0;
/*以哪个点为初始点、一共有多少条边*/
bool flag=SPFA(1,n);
for (ll i=2;i<=m;i++)
{
if(vis[i]>=inf)
{
flag=false;
break;
}
ans=ans+vis[i]*value[i];
}
if(flag) cout << ans << endl;
else cout << "No Answer" << endl;
}
return 0;
}