#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
struct Edge {
	int to, weight;
};
vector<vector<Edge>> a(N);
int n, m, k;
int ans = INF;
vector<vector<int>> dis(N, vector<int>(100, INF));
priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;

void dijkstra() {
	
	pq.push(make_tuple(0, 1, 0, 0));
	dis[1][0] = 0;
	while (!pq.empty()) {
		int cost, x, state, t;
		tie(cost, x, state, t) = pq.top();
		pq.pop();
		if (x == n && state == 0) {
			ans = min(ans, cost);
		}
		if (cost > dis[x][state]) {
			continue;
		}
		for (auto e : a[x]) {
			int y = e.to;
			int ty = e.weight;
			for (int i = 0; i < k; ++i) {
				int tt = t, next_state = (state + ty + i) % k;
				int next_time = t + ty + i;
				if (next_time < tt) {
					next_time += ((tt - next_time + k - 1) / k + 1) * k;  
				}
				if (dis[y][next_state] > next_time) {
					dis[y][next_state] = next_time; 
					pq.push(make_tuple(next_time, y, next_state, next_time)); 
				}
			}
		}
	}
}


int main() {
	int x, y, t;
	cin >> n >> m >> k;
	for (int i = 1; i <= m; ++i) {

		cin >> x >> y >> t;
		a[x].push_back({y, t});
	}
	dijkstra();
	cout << (ans != INF ? ans : -1) << endl;
	return 0;
}