#include <bits/stdc++.h>
#define ll long long
#define PII pair <int, int>
#define MP make_pair
using namespace std;
const int N = 2e4;
int n, m, k, ans = -1, l, r = (INT_MAX / 100);
//存图
vector <PII> g[N];
//第一项是是否有答案，第二项是花费时间
pair <bool, int> check (int num)
{
    //花费的时间
    int t = INT_MAX;
    queue <PII> q;
    q.push (MP (1, num * k));
    while (!q.empty ())
    {
        //现在的点
        int u = q.front ().first;
        //花费时间
        int uset = q.front ().second;
        q.pop ();
        //达到点
        if (u == n && uset % k == 0)
        {
            t = min (t, uset);
        }
        //将能走的点加入队列
        for (int i = 0; i < int (g[u].size ()); i++)
        {
            int v = g[u][i].first;
            if (uset >= g[u][i].second)
            {
                q.push (MP (v, uset + 1));
            }
        }
    }
    if (t == INT_MAX)
    {
        return MP (false, -1);
    }
    else
    {
        return MP (true, t);
    }
}
int main ()
{
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int u, v, a;
        cin >> u >> v >> a;
        g[u].push_back (MP (v, a));
    }
    //二分
    while (l <= r)
    {
        int mid = (l + r) / 2;
        pair <bool, int> tmp = check (mid);
        if (tmp.first)
        {
            r = mid - 1;
        }
        else
        {
            ans = tmp.second;
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}