这道题的可以用分层图来理解，分层图就是同一个图在z轴多了一个一样的图，每一层可以代表休息的次数，最下面为0层，这样bfs的时候，在当前节点休息就相当于优先队列中的上一个点连接到第0层的当前点，在当前节点不休息，就相当于有限队列中的上一个点连接到更高一层的当前点，这样就建立了一个立体的图，在用最短路的求法就可以解决了。 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

void solve() {
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> a(n+5);
    vector<vector<int>> g(n+5);
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
    }
    for (int i = 1; i <= m; ++i) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //当前花费 节点 不休息的次数
    priority_queue<array<int,3>,vector<array<int,3>>,greater<>> q;
    vector<vector<int>> vis(n+5,vector<int>(k+5,0));
    vector<vector<int>> ans(n+5,vector<int>(k+5,1e18));
    //k不为0时，初始时队列需要放两种状态
    if(k != 0){ //如果k不等于0，则代表第一次可以直接不休息
        q.push({1,1,1});
        ans[1][1] = 1;
    }
    //放入在第一个点休息的状态
    q.push({a[1],1,0});
    ans[1][0] = a[1];
    while (!q.empty()){
        auto [cost,now,cnt] = q.top();
        q.pop();
        if(vis[now][cnt]){
            continue;
        }
        vis[now][cnt] = 1;
        for (auto it : g[now]) {
            if(ans[it][0] > cost + a[it]){
                ans[it][0] = cost + a[it];
                q.push({cost + a[it],it,0});
            }
            if(cnt + 1 <= k && ans[it][cnt+1] > cost + 1){
                ans[it][cnt + 1] = cost + 1;
                q.push({cost + 1,it,cnt+1});
            }
        }
    }
    int minans = 1e18;
    for (int i = 0; i <= k; ++i) {
        minans = min(minans,ans[n][i]);
    }
    cout<<minans<<endl;
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}