package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"io"
	"os"
	"sort"
)

type FastScanner struct {
	data []byte
	idx  int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data}
}

func (fs *FastScanner) NextInt64() int64 {
	n := len(fs.data)
	for fs.idx < n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
	var sign int64 = 1
	if fs.idx < n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	var val int64
	for fs.idx < n {
		b := fs.data[fs.idx]
		if b < '0' || b > '9' {
			break
		}
		val = val*10 + int64(b-'0')
		fs.idx++
	}
	return val * sign
}

type Edge struct {
	to   int
	cost int64
}

type Item struct {
	d   int64
	c   int64
	idx int
}

type PQ []Item

func (pq PQ) Len() int { return len(pq) }

func (pq PQ) Less(i, j int) bool {
	if pq[i].d != pq[j].d {
		return pq[i].d < pq[j].d
	}
	if pq[i].c != pq[j].c {
		return pq[i].c > pq[j].c
	}
	return pq[i].idx < pq[j].idx
}

func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PQ) Push(x any) {
	*pq = append(*pq, x.(Item))
}

func (pq *PQ) Pop() any {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[:n-1]
	return x
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := int(in.NextInt64())
	const INF int64 = 1 << 62

	for ; t > 0; t-- {
		n := int(in.NextInt64())
		m := int(in.NextInt64())
		p := in.NextInt64()

		w := make([]int64, n)
		for i := 0; i < n; i++ {
			w[i] = in.NextInt64()
		}

		vals := append([]int64(nil), w...)
		sort.Slice(vals, func(i, j int) bool { return vals[i] < vals[j] })
		uniq := vals[:0]
		for _, x := range vals {
			if len(uniq) == 0 || uniq[len(uniq)-1] != x {
				uniq = append(uniq, x)
			}
		}

		rankMap := make(map[int64]int, len(uniq))
		for i, x := range uniq {
			rankMap[x] = i
		}
		rank := make([]int, n)
		for i := 0; i < n; i++ {
			rank[i] = rankMap[w[i]]
		}

		adj := make([][]Edge, n)
		for i := 0; i < m; i++ {
			a := int(in.NextInt64()) - 1
			b := int(in.NextInt64()) - 1
			s := in.NextInt64()
			adj[a] = append(adj[a], Edge{to: b, cost: s})
		}

		k := len(uniq)
		size := n * k
		dist := make([]int64, size)
		coins := make([]int64, size)
		for i := 0; i < size; i++ {
			dist[i] = INF
			coins[i] = -1
		}

		startH := rank[0]
		startIdx := startH
		dist[startIdx] = 0
		coins[startIdx] = p

		pq := &PQ{{d: 0, c: p, idx: startIdx}}
		heap.Init(pq)

		ans := int64(-1)

		for pq.Len() > 0 {
			it := heap.Pop(pq).(Item)
			if it.d != dist[it.idx] || it.c != coins[it.idx] {
				continue
			}

			u := it.idx / k
			h := it.idx % k

			if u == n-1 {
				ans = it.d
				break
			}

			rate := uniq[h]
			for _, e := range adj[u] {
				add := int64(0)
				if it.c < e.cost {
					add = (e.cost - it.c + rate - 1) / rate
				}
				nd := it.d + add
				nc := it.c + add*rate - e.cost
				nh := h
				if rank[e.to] > nh {
					nh = rank[e.to]
				}
				nidx := e.to*k + nh
				if nd < dist[nidx] || (nd == dist[nidx] && nc > coins[nidx]) {
					dist[nidx] = nd
					coins[nidx] = nc
					heap.Push(pq, Item{d: nd, c: nc, idx: nidx})
				}
			}
		}

		fmt.Fprintln(out, ans)
	}
}