#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const i64 INF = 0x3f3f3f3f3f3f3f3f; 

int n, m, k;
i64 d[10005][105]; 
bool vis[10005][105]; 
vector<pair<int, int>> G[10005];

void dijkstra(int s) {
    #define pli pair<i64, int> 
    priority_queue<pli, vector<pli>, greater<pli>> q;
    memset(d, 0x3f, sizeof d); 
    d[s][0] = 0; q.emplace(0, s); 
    while (!q.empty()) {
        int u = q.top().second, p = q.top().first, t; q.pop(); 
        if (vis[u][p % k]) continue; vis[u][p % k] = 1; 
        for (auto [v, w] : G[u]) {
            if (p >= w) t = p; 
            else t = ((w - p + k - 1) / k) * k + p;
            if (d[v][(t + 1) % k] > t + 1) 
                q.emplace(d[v][(t + 1) % k] = t + 1, v); 
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m >> k; 
    while (m--) {
        int u, v, w; cin >> u >> v >> w; 
        G[u].emplace_back(v, w); 
    }
    dijkstra(1);
    if (d[n][0] == INF) cout << "-1\n"; 
    else cout << d[n][0] << "\n"; 
    return 0;
}