#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,q;
vector<int> con[200005], arb[200005];
int s[200005];
namespace DSU
{
int father[200005], siz[200005], strongest[200005];
void init()
{
for(int i=1;i<=n;i++)
{
father[i] = i;
siz[i] = 1;
strongest[i] = i;
}
}
int get(int x)
{
if(father[x] != x)
father[x] = get(father[x]);
return father[x];
}
void unite(int x, int y)
{
x = get(x);
y = get(y);
if(x == y)
return;
if(siz[x] < siz[y])
swap(x,y);
siz[x] += siz[y];
father[y] = x;
if(s[strongest[y]] > s[strongest[x]])
strongest[x] = strongest[y];
}
}
int dp[2][3005][3005], newdp[2][3005];
int siz[3005];
void dfs(int nod, int par, int root)
{
for(int adj:arb[nod])
{
if(adj == par)
continue;
dfs(adj, nod, root);
}
siz[nod] = 0;
dp[0][nod][0] = 0;
dp[1][nod][0] = INF;
for(int adj:arb[nod])
{
if(adj == par)
continue;
for(int x=0;x<=siz[nod]+siz[adj];x++)
for(int c=0;c<2;c++)
newdp[c][x] = INF;
for(int x=0;x<=siz[nod];x++)
{
for(int y=0;y<=siz[adj];y++)
{
for(int cx=0;cx<2;cx++)
{
for(int cy=0;cy<2;cy++)
{
if(cx && cy)
continue;
newdp[cx + cy][x + y] = min(newdp[cx + cy][x + y], dp[cx][nod][x] + dp[cy][adj][y]);
}
}
}
}
for(int x=0;x<=siz[nod]+siz[adj];x++)
for(int c=0;c<2;c++)
dp[c][nod][x] = newdp[c][x];
siz[nod] += siz[adj];
}
/*for(int c=0;c<2;c++)
for(int x=0;x<=siz[nod];x++)
cerr<<c<<" "<<nod<<" "<<x<<": "<<dp[c][nod][x]<<" dp before\n";*/
for(int c=0;c<2;c++)
{
for(int x=0;x<=siz[nod];x++)
newdp[c][x] = dp[c][nod][x];
newdp[c][siz[nod] + 1] = INF;
dp[c][nod][siz[nod] + 1] = INF;
}
siz[nod]++;
for(int x=0;x<=siz[nod];x++)
{
if(par != -1) newdp[0][x] = min(newdp[0][x], dp[1][nod][x] - (s[nod] + s[par]));
if(x + 1 <= siz[nod]) newdp[1][x + 1] = min(newdp[1][x + 1], dp[0][nod][x] + (s[nod] + s[root]));
if(x + 1 <= siz[nod] && par != -1) newdp[0][x + 1] = min(newdp[0][x + 1], dp[0][nod][x] + (s[nod] + s[root]) - (s[nod] + s[par]));
}
for(int x=0;x<=siz[nod];x++)
for(int c=0;c<2;c++)
dp[c][nod][x] = newdp[c][x];
/*for(int c=0;c<2;c++)
for(int x=0;x<=siz[nod];x++)
cerr<<c<<" "<<nod<<" "<<x<<": "<<dp[c][nod][x]<<" dp\n";*/
}
vector<int> get_mst(int q)
{
vector<pair<int, pair<int,int>>> edges;
for(int i=1;i<=n;i++)
{
for(int j:con[i])
{
if(j <= i)
continue;
edges.push_back({s[i] + s[j], {i, j}});
}
}
sort(edges.begin(), edges.end());
vector<int> deg(n+2,0);
DSU::init();
for(auto [c,e]:edges)
{
if(DSU::get(e.first) != DSU::get(e.second))
{
DSU::unite(e.first, e.second);
deg[e.first]++;
deg[e.second]++;
arb[e.first].push_back(e.second);
arb[e.second].push_back(e.first);
}
}
vector<int> idk;
int root = 1;
for(int i=1;i<=n;i++)
if(s[i] < s[root])
root = i;
vector<int> rez(q+2, 0);
/*for(int r=1;r<=n;r++)
{
if(s[r] == s[root])
{
//dfs(r, -1, r);
for(int cate=1;cate<=q;cate++)
sum = min(sum, dp[0][r][cate]);
}
}*/
dfs(root, -1, root);
for(int cate=1;cate<=q;cate++)
rez[cate] = min(rez[cate], dp[0][root][cate]);
for(int cate=1;cate<=q;cate++)
rez[cate] = min(rez[cate], rez[cate - 1]);
int aux = 0;
for(int i=1;i<=n;i++)
aux += s[i] * deg[i];
for(int cate=0;cate<=q;cate++)
rez[cate] += aux;
return rez;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
cin>>s[i];
int u,v;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
con[u].push_back(v);
con[v].push_back(u);
}
vector<int> rez = get_mst(q);
int maxs = 0, aux = 0;
for(int u=1;u<=n;u++)
{
maxs = max(maxs, s[u]);
aux -= s[u];
}
aux += maxs;
for(int cnt=0;cnt<=q;cnt++)
cout<<rez[cnt] + aux<<"\n";
return 0;
}
