1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<bits/stdc++.h>
using namespace std;
#define P pair<ll,ll>
#define INF 0x7fffffff
#define Debug(x) cout<<#x<<" :"<<x<<endl;
typedef long long ll;
const ll maxn=55;
const ll maxm=5000;
struct Edge{
ll to,w,nx;
}e[maxm];
ll head[maxn],path[maxm],d[maxn],vis[maxn],val[maxm],ans[maxn];
ll n,m,start,tmp=1;
priority_queue<P,vector<P>,greater<P>> q;
void add(ll u,ll v,ll w){
e[tmp]={v,w,head[u]};head[u]=tmp++;
}
void dijkstra(){
q.push({0,start});d[start]=0;
while(!q.empty()){
ll u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(ll i=head[u];i;i=e[i].nx){
ll v=e[i].to;
if(d[u]+1<d[v]){
d[v]=d[u]+1;
q.push({d[v],v});
}
}
}
}
void dfs(ll u,ll sum){
ans[u]=min(ans[u],sum);
for(ll i=head[u];i;i=e[i].nx){
ll v=e[i].to;
if(d[v]==d[u]+1){
ll c=e[i].w;
path[c]++;
dfs(v,sum+path[c]*val[c]);
path[c]--;
}
}
}
void solve(){
start=1;memset(d,0x1f,sizeof(d));
dijkstra();
memset(ans,0x1f,sizeof(ans));
memset(path,0,sizeof(path));
dfs(1,0);
for(ll i=2;i<=n;i++) cout<<ans[i]<<endl;
}
int main(){
cin>>n>>m;
for(ll i=1;i<=m;i++){
cin>>val[i];
}
for(ll i=1;i<=m;i++){
ll u,v,w;cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
solve();
return 0;
}
|
