import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

class Graph{
	int vertex;
	LinkedList<Pair>[] adj;
	int distance[];
	int id[];

	public Graph(int vertex) {
		this.vertex = vertex;
		adj = new LinkedList[vertex];
		distance = new int[vertex];
		id = new int[vertex];
		Arrays.fill(distance, Integer.MAX_VALUE);			//Maybe TLE's? idk man
		for(int i = 0; i < vertex; i++)
		{
			adj[i] = new LinkedList();
		}
	}

	public void addEdge(int u, int v, int w) {
		Pair one = new Pair(w, u);
		Pair two = new Pair(w, v);
		adj[v].add(one);
		adj[u].add(two);
	}

	public void shortestPath(int src) {
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		pq.add(new Pair(0, src));
		distance[src] = 0;

		while(!pq.isEmpty())
		{
			Pair p = pq.poll();
			int node = p.vertex;

			for(Pair neighbor : adj[node]) {
				int v = neighbor.vertex;
				int w = neighbor.weight;
				if(distance[v] > distance[node] + w) {
					distance[v] = distance[node] + w;
					id[v] = node;
					pq.add(new Pair(distance[node], v));
				}
			}
		}

	}

	public void printGraph() {
		for(int i = 0; i < vertex; i++)
		{
			if(adj[i].size() > 0) {
				System.out.print("Node " + i + " is connected to ");

				for(Pair j : adj[i]) {
					System.out.print(j + " ");
				}
			}
			System.out.println();
		}
	}
}

class Pair implements Comparable<Pair>{
	public int weight;
	public int vertex;

	public Pair(int w, int v) {
		weight = w;
		vertex = v;
	}

	public int compareTo(Pair p)
	{
		int diff = this.weight-p.weight;
		if(diff == 0) diff = this.vertex-p.vertex;
		return diff;
	}

	public String toString() {
		return "vertex " + vertex + " with weight " + weight;
	}
}

//WEIGHT FIRST, NODE SECOND
public class shortcut {
	public static void main(String[] args)throws IOException
	{
		Scanner kb = new Scanner(new File("shortcut.in"));
		PrintWriter pw = new PrintWriter(new FileWriter(new File("shortcut.out")));

		//DETERMINE HOW MANY COWS VISIT A GIVEN NODE ON THEIR WAY TO THE BARN
		//USE IDS SIMILAR TO CODEFORCES DIJKSTRAS

		//RUN SHORTEST PATH FROM BARN
		//TRY MAKING A BACKPATH FROM BARN TO EVERY SINGLE NODE
		int N = kb.nextInt();
		int M = kb.nextInt();
		int T = kb.nextInt();

		Graph g = new Graph(N);

		int[] cows = new int[N];
		for(int i = 0; i < N; i++)
		{
			cows[i] = kb.nextInt();
		}

		for(int i = 0; i < M; i++)	//MAY BE SOME TROUBLE WITH NODE ID's
		{
			int x = kb.nextInt();
			int y = kb.nextInt();
			int w = kb.nextInt();
			x--;
			y--;
			//System.out.println(x + " " + y);
			g.addEdge(x, y, w);
		}

		g.shortestPath(0);

		//dfs from each pasture i and add cows[i] to every pasture along the way
		int[] cowspassingthrough = new int[N];
		for(int i = 1; i < N; i++)
		{
			int cowstoadd = cows[i];
			int curr = i;
			while(curr!=0) {
				cowspassingthrough[curr]+=cowstoadd;
				curr = g.id[curr];
			}

		}

		/**for(int i = 0; i < N; i++)
		{
			System.out.println("distance from barn to pasture i = " + i + " is " + g.distance[i]);
		}**/
		int ans = 0;
		for(int i = 1; i < N; i++)
		{
			ans = Math.max(ans, cowspassingthrough[i]*(g.distance[i]-T));
		}
		pw.println(ans);
		pw.close();
	}
}