#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using str = string;

static int intMin = numeric_limits<int>::min();
static int intMax = numeric_limits<int>::max();
static long long longMin = numeric_limits<long long>::min();
static long long longMax = numeric_limits<long long>::max();
const ll INF = 1e9 + 7;
static ll mod = 998244353;
static long long di[] = { -1, 0, 1, 0, -1, -1, 1, 1};
static long long dj[] = { 0, 1, 0, -1, -1, 1, -1, 1};

class ReadArray { public:
    vector<int> in() { string s; getline(cin >> ws, s); istringstream is(s); return vector<int>(istream_iterator<int>(is), {}); }
    vector<long long> ll() { string s; getline(cin >> ws, s); istringstream is(s); return vector<long long>(istream_iterator<long long>(is), {}); }
    vector<float> fl() { string s; getline(cin >> ws, s); istringstream is(s); return vector<float>(istream_iterator<float>(is), {}); }
    vector<double> dbl() { string s; getline(cin >> ws, s); istringstream is(s); return vector<double>(istream_iterator<double>(is), {}); }
    vector<string> str() { string s; getline(cin >> ws, s); istringstream is(s); return vector<string>(istream_iterator<string>(is), {}); }
    vector<char> ch() { string s; getline(cin >> ws, s); istringstream is(s); vector<char> v; for (char c; is >> c;) v.push_back(c); return v; }
}; ReadArray readArray;
class ReadMap { public:
    vector<vector<int>> in(int h, int w) { vector<vector<int>> r(h,vector<int>(w)); for(int i=0;i<h;i++){auto s = readArray.in(); for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
    vector<vector<long long>> ll(int h, int w) { vector<vector<long long>> r(h,vector<long long>(w)); for(int i=0;i<h;i++){auto s = readArray.ll(); for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
    vector<vector<char>> ch(int h, int w) { vector<vector<char>> r(h,vector<char>(w)); for(int i=0;i<h;i++){string s; cin >> s; for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
    vector<vector<bool>> bo(int h, int w, char c = '.') { vector<vector<bool>> r(h,vector<bool>(w)); for(int i=0;i<h;i++){string s; cin >> s; for(int j=0;j<w;j++) r.at(i).at(j)=(s.at(j)==c);} return r;}
};
class ReadFunctions { public:
    int in() { int x; scanf("%d", &x); return x; }
    auto in2() { int x, y; scanf("%d %d", &x, &y); return make_tuple(x, y); }
    auto in3() { int x, y, z; scanf("%d %d %d", &x, &y, &z); return make_tuple(x, y, z); }
    auto in4() { int x, y, z, w; scanf("%d %d %d %d", &x, &y, &z, &w); return make_tuple(x, y, z, w); }
    auto in5() { int x, y, z, w, u; scanf("%d %d %d %d %d", &x, &y, &z, &w, &u); return make_tuple(x, y, z, w, u); }
    auto in6() { int x, y, z, w, u, v; scanf("%d %d %d %d %d %d", &x, &y, &z, &w, &u, &v); return make_tuple(x, y, z, w, u, v); }
    long long ll() { long long x; scanf("%lld", &x); return x; }
    auto ll2() { long long x, y; scanf("%lld %lld", &x, &y); return make_tuple(x, y); }
    auto ll3() { long long x, y, z; scanf("%lld %lld %lld", &x, &y, &z); return make_tuple(x, y, z); }
    auto ll4() { long long x, y, z, w; scanf("%lld %lld %lld %lld", &x, &y, &z, &w); return make_tuple(x, y, z, w); }
    auto ll5() { long long x, y, z, w, u; scanf("%lld %lld %lld %lld %lld", &x, &y, &z, &w, &u); return make_tuple(x, y, z, w, u); }
    auto ll6() { long long x, y, z, w, u, v; scanf("%lld %lld %lld %lld %lld %lld", &x, &y, &z, &w, &u, &v); return make_tuple(x, y, z, w, u, v); }
    float fl() { float x; scanf("%f", &x); return x; }
    double dbl() { double x; scanf("%lf", &x); return x; }
    string str() { string x; cin >> x; return x; }
    char cha() { char x; scanf(" %c", &x); return x; }
    
    ReadArray array;
    ReadMap map;
}; ReadFunctions re;

void write(string s) { printf("%s\n", s.c_str()); }
void write(char c) { printf("%c\n", c); }
void write(int n) { printf("%i\n", n); }
void write(long long n) { printf("%lld\n", n); }
void write(double n) { printf("%.10f\n", n); }
void write(bool a) { printf("%s\n", a ? "Yes" : "No"); }
void writeMinus1() {printf("%i\n", -1);}

/* keysにそってvalueをソート */
template <typename T> void Sort(std::vector<T>& keys, std::vector<T>& values) {
    std::vector<std::pair<T, T>> paired;
    for (size_t i = 0; i < keys.size(); ++i) {
        paired.emplace_back(keys[i], values[i]);
    }
    std::sort(paired.begin(), paired.end());
    for (size_t i = 0; i < keys.size(); ++i) {
        keys[i] = paired[i].first;
        values[i] = paired[i].second;
    }
}
template <typename T> void Sort(vector<T> &array) {sort(array.begin(), array.end());}
template <typename T> void Reverse(vector<T> &array) {reverse(array.begin(), array.end());}

struct pair_hash {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ (h2 << 1); // XORとビットシフトを利用してハッシュを合成
    }
};
struct tuple_hash {
    template <typename... T>
    size_t operator()(const tuple<T...>& t) const {
        size_t seed = 0;
        apply([&seed](const auto&... args) {
            ((seed ^= 
                hash<decay_t<decltype(args)>>{}(args)
                + 0x9e3779b97f4a7c15ULL
                + (seed << 6)
                + (seed >> 2)
            ), ...);
        }, t);
        return seed;
    }
};

long long average(long long a, long long b) {return a + (b - a) / 2; }
long long kaijou(long long v) { long long r = 1; for (long long i = v; i > 0; i--) r *= i; return r; }
long long yojou(int v, int v2) { long long r = v % v2; return r < 0 ? r + v2 : r; }
long long yojou(ll v, ll v2) { long long r = v % v2; return r < 0 ? r + v2 : r; }
int digit_count(long long n) {if(n==0)return 1;n=llabs(n);int cnt=0;while(n>0){cnt++;n/=10;}return cnt;}
bool rangeCheck(int i, int j, int h, int w) { return (0 <= i && i < h && 0 <= j && j < w);}
long long power(long long base, long long exp) { long long result = 1; for (int i = 0; i < exp; ++i) result *= base; return result; }
long long modPow(long long r, long long n) {long long res = 1; r %= mod; while (n > 0) { if (n & 1) res *= r; res %= mod; r *= r; r %= mod; n >>= 1;} return res % mod;}
long long modinv(long long a) { ll b = mod, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);	} u %= mod; if (u < 0) u += mod; return u; }
int popcount(ll num) {int count = 0;while(num){count+=num&1;num>>=1;}return count;}
long long GCD(long long a, long long b) {if(b==0)return a;return GCD(b,a%b);}

mt19937 rng(123456);  // 固定seed（好きな数字でOK）
// [l, r] の整数乱数
int rand_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}
// [0, 1) の実数乱数
double rand_double() {
    uniform_real_distribution<double> dist(0.0, 1.0);
    return dist(rng);
}

struct UnionFind {
    vector<int> parent, rank, parity; 
    // parity[x] : 親との色差（0=同色, 1=異色）

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        parity.resize(n, 0);
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    pair<int,int> find(int x) {
        if(parent[x] == x) return {x, 0};
        auto [r, p] = find(parent[x]);
        parity[x] ^= p;
        parent[x] = r;
        return {parent[x], parity[x]};
    }

    // 戻り値: {親になった根, 子になった根, 子を反転する必要があるか}
    tuple<int,int,bool> unite(int x, int y) {
        auto [rx, px] = find(x);
        auto [ry, py] = find(y);

        if(rx == ry) {
            return {rx, ry, false};
        }

        bool needFlip = ((px ^ py) == 0);

        if(rank[rx] < rank[ry]) {
            swap(rx, ry);
            swap(px, py);
        }

        parent[ry] = rx;
        parity[ry] = px ^ py ^ 1;

        if(rank[rx] == rank[ry]) rank[rx]++;

        return {rx, ry, needFlip};
    }
};

template <typename T> int FindEqual(vector<T> &vec, T target) {
    int l = 0; int r = vec.size()-1;
    int ret = -1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(vec.at(mid) > target) {
            r = mid - 1;
        }
        else if(vec.at(mid) == target)
        {
            ret = mid;
            break;
        }
        else l = mid + 1;
    }
    return ret;
}
template <typename T> int FindFirstGreater(vector<T> &vec, T target) {
    int l = 0; int r = vec.size()-1;
    int ret = -1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(vec.at(mid) >= target) {
            ret = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ret;
}
template <typename T> int FindFirstLess(vector<T> &vec, T target) {
    int l = 0; int r = vec.size()-1;
    int ret = -1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(vec.at(mid) <= target) {
            ret = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return ret;
}

class SegmentTreeSum {
private:
    std::vector<long long> tree; // セグメントツリー
    int size; // 配列のサイズ

    // セグメントツリーの構築
    void build(const std::vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            // 葉ノードの場合
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            // 左右の子ノードを再帰的に構築
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            // 子ノードをマージ
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    // 範囲クエリ
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            // 範囲外の場合
            return 0;
        }
        if (l <= start && end <= r) {
            // 完全に範囲内の場合
            return tree[node];
        }
        // 範囲が部分的に重なる場合
        int mid = (start + end) / 2;
        long long leftSum = query(2 * node + 1, start, mid, l, r);
        long long rightSum = query(2 * node + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // 値の更新
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            // 葉ノードを更新
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                // 左部分木を更新
                update(2 * node + 1, start, mid, idx, val);
            } else {
                // 右部分木を更新
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            // 子ノードの値を基に現在のノードを更新
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

public:
    // コンストラクタ: 配列を受け取り、セグメントツリーを構築
    SegmentTreeSum(const std::vector<int>& arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(arr, 0, 0, size - 1);
    }

    // 範囲クエリの公開メソッド
    long long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    // 値の更新の公開メソッド
    void update(int idx, int val) {
        update(0, 0, size - 1, idx, val);
    }
};
class SegmentTreeMax {
private:
    std::vector<long long> tree; // セグメントツリー（区間の最大値）
    int size; // 配列のサイズ

    // セグメントツリーの構築
    void build(const std::vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            // 葉ノードの場合
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            // 左右の子ノードを再帰的に構築
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            // 子ノードをマージ（最大値を保持）
            tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    // 範囲クエリ（最大値を取得）
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            // 範囲外の場合（最小値を返す）
            return LLONG_MIN;
        }
        if (l <= start && end <= r) {
            // 完全に範囲内の場合
            return tree[node];
        }
        // 範囲が部分的に重なる場合
        int mid = (start + end) / 2;
        long long leftMax = query(2 * node + 1, start, mid, l, r);
        long long rightMax = query(2 * node + 2, mid + 1, end, l, r);
        return std::max(leftMax, rightMax); // 最大値を取得
    }

    // 値の更新
    void update(int node, int start, int end, int idx, long long val) {
        if (start == end) {
            // 葉ノードを更新
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                // 左部分木を更新
                update(2 * node + 1, start, mid, idx, val);
            } else {
                // 右部分木を更新
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            // 親ノードの値を更新（最大値を保持）
            tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    // コンストラクタ: 配列を受け取り、セグメントツリーを構築
    SegmentTreeMax(const std::vector<long long>& arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(arr, 0, 0, size - 1);
    }

    // 範囲クエリ（最大値）の公開メソッド
    long long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    // 値の更新の公開メソッド
    void update(int idx, long long val) {
        update(0, 0, size - 1, idx, val);
    }
};
class SegmentTreeMin {
private:
    std::vector<long long> tree; // セグメントツリー（区間の最小値）
    int size; // 配列のサイズ

    // セグメントツリーの構築
    void build(const std::vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    // 範囲クエリ（最小値を取得）
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return LLONG_MAX; // 範囲外なら最大値を返す（最小値を取るため）
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        long long leftMin = query(2 * node + 1, start, mid, l, r);
        long long rightMin = query(2 * node + 2, mid + 1, end, l, r);
        return std::min(leftMin, rightMin); // 最小値を取得
    }

    // 値の更新
    void update(int node, int start, int end, int idx, long long val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    SegmentTreeMin(const std::vector<long long>& arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(arr, 0, 0, size - 1);
    }

    long long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    void update(int idx, long long val) {
        update(0, 0, size - 1, idx, val);
    }
};

class LazySegmentTreeSum {
private:
    int n;                           // 配列のサイズ
    vector<long long> tree;          // セグメントツリーのデータ
    vector<long long> lazy;          // 遅延評価用のデータ

    // 区間の合計を計算する (加算クエリに対応)
    void apply(int node, int start, int end, long long value) {
        tree[node] += value * (end - start + 1); // ノードの値を更新
        if (start != end) { // 子ノードが存在する場合
            lazy[node * 2] += value;     // 左の子ノードに遅延を追加
            lazy[node * 2 + 1] += value; // 右の子ノードに遅延を追加
        }
    }

    // 遅延を伝播する
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) { // 遅延が存在する場合
            apply(node, start, end, lazy[node]);
            lazy[node] = 0; // 遅延をクリア
        }
    }

    // 区間更新 (内部)
    void updateRange(int node, int start, int end, int l, int r, long long value) {
        propagate(node, start, end); // 遅延を反映

        if (start > r || end < l) return; // 完全に範囲外
        if (start >= l && end <= r) {     // 完全に範囲内
            apply(node, start, end, value);
            return;
        }

        // 部分的に範囲内
        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, value);
        updateRange(node * 2 + 1, mid + 1, end, l, r, value);
        tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 子ノードの結果を合成
    }

    // 区間クエリ (内部)
    long long queryRange(int node, int start, int end, int l, int r) {
        propagate(node, start, end); // 遅延を反映

        if (start > r || end < l) return 0; // 完全に範囲外
        if (start >= l && end <= r) return tree[node]; // 完全に範囲内

        // 部分的に範囲内
        int mid = (start + end) / 2;
        long long left = queryRange(node * 2, start, mid, l, r);
        long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
        return left + right; // 子ノードの結果を合成
    }

public:
    LazySegmentTreeSum(int size) {
        n = size;
        tree.resize(4 * n, 0); // セグメントツリーのサイズ
        lazy.resize(4 * n, 0); // 遅延配列のサイズ
    }

    // 区間更新
    void update(int l, int r, long long value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区間クエリ
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};
class LazySegmentTreeMax {
private:
    int n;                            // 配列サイズ
    vector<long long> tree;           // 区間最大値
    vector<long long> lazy;           // 遅延加算

    // 遅延値をノードに適用
    void apply(int node, int start, int end, long long value) {
        tree[node] += value;          // 最大値に加算
        if (start != end) {           // 葉でなければ子へ遅延伝播
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
    }

    // 遅延伝播
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) {
            apply(node, start, end, lazy[node]);
            lazy[node] = 0;
        }
    }

    // 区間更新
    void updateRange(int node, int start, int end,
                     int l, int r, long long value) {
        propagate(node, start, end);

        if (start > r || end < l) return; // 範囲外

        if (start >= l && end <= r) {     // 完全包含
            apply(node, start, end, value);
            return;
        }

        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, value);
        updateRange(node * 2 + 1, mid + 1, end, l, r, value);

        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    // 区間クエリ
    long long queryRange(int node, int start, int end,
                         int l, int r) {
        propagate(node, start, end);

        if (start > r || end < l) return LLONG_MIN; // 単位元
        if (start >= l && end <= r) return tree[node];

        int mid = (start + end) / 2;
        long long left = queryRange(node * 2, start, mid, l, r);
        long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);

        return max(left, right);
    }

public:
    LazySegmentTreeMax(int size) {
        n = size;
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
    }

    // 区間加算
    void update(int l, int r, long long value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区間最大値取得
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};
class LazySegmentTreeMin {
private:
    int n;                            // 配列のサイズ
    vector<long long> tree;           // 区間最小値を保持
    vector<long long> lazy;           // 遅延加算を保持

    // 遅延を適用
    void apply(int node, int start, int end, long long value) {
        tree[node] += value; // 区間の最小値を一括加算
        if (start != end) { // 葉でなければ子に遅延を伝える
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
    }

    // 遅延を伝播
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) {
            apply(node, start, end, lazy[node]);
            lazy[node] = 0;
        }
    }

    // 区間更新 (内部)
    void updateRange(int node, int start, int end, int l, int r, long long value) {
        propagate(node, start, end);

        if (start > r || end < l) return; // 範囲外
        if (start >= l && end <= r) {     // 完全に範囲内
            apply(node, start, end, value);
            return;
        }

        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, value);
        updateRange(node * 2 + 1, mid + 1, end, l, r, value);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    // 区間クエリ (内部)
    long long queryRange(int node, int start, int end, int l, int r) {
        propagate(node, start, end);

        if (start > r || end < l) return LLONG_MAX; // 範囲外は無限大
        if (start >= l && end <= r) return tree[node];

        int mid = (start + end) / 2;
        long long left = queryRange(node * 2, start, mid, l, r);
        long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
        return min(left, right);
    }

public:
    LazySegmentTreeMin(int size) {
        n = size;
        tree.resize(4 * n, 0);  // 区間最小値 (初期値は0で構築)
        lazy.resize(4 * n, 0);  // 遅延配列
    }

    // 区間更新
    void update(int l, int r, long long value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区間クエリ
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};

vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}
/*  nCk :modでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k) {
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

int main() 
{
    auto[n,m,k] = re.ll3();
    auto c = re.array.ll();

    vector<vector<pair<ll,ll>>> con(n*(k+1));
    for(int i = 0; i < m; i++)
    {
        auto[u,v] = re.ll2();

        u--; v--;

        con.at(u).push_back({v,c.at(i)});
        con.at(v).push_back({u,c.at(i)});
        for(int j = 1; j <= k; j++)
        {
            con.at(u+n*j).push_back({v+n*j,c.at(i)});
            con.at(v+n*j).push_back({u+n*j,c.at(i)});
            con.at(u+n*(j-1)).push_back({v+n*j,0});
            con.at(v+n*(j-1)).push_back({u+n*j,0});
        }
    }

    priority_queue<pair<ll,ll>> q;
    q.push({0,0});
    vector<ll> dis(n*(k+1),longMax);
    dis.at(0) = 0;

    while(q.size())
    {
        auto[d,i] = q.top();
        d *= -1;
        q.pop();

        if(dis.at(i) < d) continue;

        if(i%n == n-1)
        {
            write(d);
            return 0;
        }

        for(auto[j,w] : con.at(i))
        {
            if(dis.at(j) > d+w)
            {
                dis.at(j) = d+w;
                q.push({-d-w, j});
            }
        }
    }

    writeMinus1();
}