// E. Magical Permutation
// time limit per test1 second
// memory limit per test256 megabytes
// inputstandard input
// outputstandard output
// Kuro has just learned about permutations and he is really excited to create a
// new permutation type. He has chosen 𝑛 distinct positive integers and put all
// of them in a set 𝑆. Now he defines a magical permutation to be:

// A permutation of integers from 0 to 2𝑥−1, where 𝑥 is a non-negative integer.
// The bitwise xor of any two consecutive elements in the permutation is an
// element in 𝑆. Since Kuro is really excited about magical permutations, he
// wants to create the longest magical permutation possible. In other words, he
// wants to find the largest non-negative integer 𝑥 such that there is a magical
// permutation of integers from 0 to 2𝑥−1. Since he is a newbie in the subject,
// he wants you to help him find this value of 𝑥 and also the magical
// permutation for that 𝑥.

// Input
// The first line contains the integer 𝑛 (1≤𝑛≤2⋅105) — the number of elements in
// the set 𝑆.

// The next line contains 𝑛 distinct integers 𝑆1,𝑆2,…,𝑆𝑛 (1≤𝑆𝑖≤2⋅105) — the
// elements in the set 𝑆.

// Output
// In the first line print the largest non-negative integer 𝑥, such that there
// is a magical permutation of integers from 0 to 2𝑥−1.

// Then print 2𝑥 integers describing a magical permutation of integers from 0 to
// 2𝑥−1. If there are multiple such magical permutations, print any of them.

// Examples
// inputCopy
// 3
// 1 2 3
// outputCopy
// 2
// 0 1 3 2
// inputCopy
// 2
// 2 3
// outputCopy
// 2
// 0 2 1 3
// inputCopy
// 4
// 1 2 3 4
// outputCopy
// 3
// 0 1 3 2 6 7 5 4
// inputCopy
// 2
// 2 4
// outputCopy
// 0
// 0
// inputCopy
// 1
// 20
// outputCopy
// 0
// 0
// inputCopy
// 1
// 1
// outputCopy
// 1
// 0 1
// Note
// In the first example, 0,1,3,2 is a magical permutation since:

// 0⊕1=1∈𝑆
// 1⊕3=2∈𝑆
// 3⊕2=1∈𝑆
// Where ⊕ denotes bitwise xor operation.

#include <bits/stdc++.h>

constexpr long long INF = 1LL << 62;

using namespace std;

int n, m;
int i, j, k;

struct Edge {
  int src, dst, cost;
  Edge(int s, int d, int c = 1) : src(s), dst(d), cost(c) {}
  bool operator<(const Edge &e) { return cost < e.cost; }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

// O(|V||E|)
bool bellman_ford(int s, Graph &g, vector<long> &dist) {
  int n = g.size();
  dist.assign(n, INF);
  dist[s] = 0;

  for (int i = 0; i < n * 2; ++i) {
    bool update = false;
    for (int v = 0; v < n; ++v) {
      for (Edge e : g[v]) {
        if (dist[e.src] != INF && dist[e.dst] > dist[e.src] + e.cost) {
          dist[e.dst] = dist[e.src] + e.cost;
          update = true;

          if (i >= n && e.dst == n - 1) {
            // negative cycle
            return true;
          }
        }
      }
    }
    if (!update) break;
  }
  return false;
}

void solve() {
  int p;
  int a, b, c;
  cin >> n >> m >> p;

  Graph g(n);
  for (i = 0; i < m; ++i) {
    cin >> a >> b >> c;
    --a, --b;
    c -= p;
    g[a].emplace_back(a, b, -c);
  }
  vector<long> dist(n);

  if (bellman_ford(0, g, dist)) {
    cout << -1 << endl;
    return;
  } else {
    cout << max(-dist[n - 1], 0l) << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
  return 0;
}


Measured memory_bytes: 512