#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
struct node
{
    int next, to, dis;
} e[20001];
int n, m, k;
int cnt;
int h[10001];
bool vis[10001][101];
int ans[10001][101];
priority_queue<pii, vector<pii>, greater<pii>> q;
void add_edge(int a, int b, int c)
{
    e[++cnt].to = b;
    e[cnt].dis = c;
    e[cnt].next = h[a];
    h[a] = cnt;
}
void dijkstra()
{
    memset(ans, 0x3f, sizeof(ans));
    ans[1][0] = 0;
    q.push({0, 1});
    while (!q.empty())
    {
        int t = q.top().first, p = q.top().second;
        q.pop();
        if (vis[p][t % k])
            continue;
        vis[p][t % k] = 1;
        for (int i = h[p]; i; i = e[i].next)
        {
            if (t > e[i].dis)
            {
                if (ans[e[i].to][(t + 1) % k] > t + 1)
                {
                    ans[e[i].to][(t + 1) % k] = t + 1;
                    q.push({t + 1, e[i].to});
                }
            }
            else
            {
                t += ((e[i].dis - t + k - 1) / k) * k;
                if (ans[e[i].to][(t + 1) % k] > t + 1)
                {
                    ans[e[i].to][(t + 1) % k] = t + 1;
                    q.push({t + 1, e[i].to});
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    dijkstra();
    if (ans[n][0] == 1061109567)
        puts("-1");
    else
        printf("%d", ans[n][0]);
    return 0;
}