题目内容

在一片大陆上，有 $n$ 座城市，编号为 $1$ 到 $n$，城市之间有 $m$ 条有向道路。第 $i$ 条道路从城市 $u_i$ 通往城市 $v_i$，通行费为 $w_i$。一位旅行者打算从城市 $1$ 出发，前往城市 $n$，并且他恰好携带 $E$ 元，希望将钱全部花完，不多不少。请你计算有多少种不同的路线，使得总通行费恰好等于 $E$。

两条路线视为不同，当且仅当它们经过的道路序列不同。注意，可能有多条道路连接相同的两个城市且费用相同，每一条都应视为不同的选择。

输入保证：城市数量 $n$ 满足 $1 \le n \le 100$，道路数量 $m$ 满足 $1 \le m \le 1000$，旅行者的预算 $E$ 满足 $1 \le E \le 1000$，每条道路的费用 $w_i$ 满足 $1 \le w_i \le E$。

输入描述

第一行包含三个整数 $n, m, E$，分别表示城市数量、有向道路数量和旅行者的预算。 接下来 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示一条从 $u_i$ 到 $v_i$ 的有向道路，其通行费为 $w_i$。