use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::{fastout, input, marker::Usize1};

const DIRS: [(isize, isize); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];

trait OrdExt {
    fn chmax(&mut self, other: Self) -> bool;
    fn chmin(&mut self, other: Self) -> bool;
}

impl<T: Ord> OrdExt for T {
    fn chmax(&mut self, other: Self) -> bool {
        if *self < other {
            *self = other;
            true
        } else {
            false
        }
    }

    fn chmin(&mut self, other: Self) -> bool {
        if *self > other {
            *self = other;
            true
        } else {
            false
        }
    }
}

#[fastout]
fn main() {
    input! {
        N: usize,
        M: usize,
        K: usize,
        C: [usize; M],
        edges: [(Usize1, Usize1); M],
    }

    let mut graph = vec![vec![]; N];

    for (i, &(a, b)) in edges.iter().enumerate() {
        graph[a].push((b, C[i]));
        graph[b].push((a, C[i]));
    }

    let mut priq = BinaryHeap::new();
    let mut locked = vec![vec![false; K + 1]; N];
    let mut dist = vec![vec![std::usize::MAX / 4; K + 1]; N];

    priq.push(Reverse((0, 0, K)));

    while let Some(Reverse((d, v, k))) = priq.pop() {
        if locked[v][k] {
            continue;
        }
        locked[v][k] = true;

        for &(w, c) in graph[v].iter() {
            if locked[w][k] {
                continue;
            }

            if dist[w][k].chmin(d + c) {
                priq.push(Reverse((dist[w][k], w, k)));
            }

            if k > 0 && dist[w][k - 1].chmin(d) {
                priq.push(Reverse((dist[w][k - 1], w, k - 1)));
            }
        }
    }

    let &ans = dist[N - 1].iter().min().unwrap();

    if ans == std::usize::MAX / 4 {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}