import sys, heapq
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def solve():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))
    g = []
    for _ in range(n + 1):
        g.append([])
    e = []
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        t = int(next(it))
        g[u].append((v, t))
        g[v].append((u, t))
        e.append((u, v, t))
    INF = 10 ** 30
    d = [INF] * (n + 1)
    d[1] = 0
    que = [(0, 1)]
    while que:
        cur, v = heapq.heappop(que)
        if cur > d[v]:
            continue
        for j in range(len(g[v])):
            u = g[v][j][0]
            t = g[v][j][1]
            nxt = cur + t
            if nxt < d[u]:
                d[u] = nxt
                heapq.heappush(que, (nxt, u))
    gd = 0
    for i in range(len(e)):
        u = e[i][0]
        v = e[i][1]
        t = e[i][2]
        if d[u] != INF:
            gd = gcd(gd, abs(d[u] + t - d[v]))
        if d[v] != INF:
            gd = gcd(gd, abs(d[v] + t - d[u]))
    if gd == 0:
        ans = d[n] % k
    else:
        ans = d[n] % gcd(gd, k)
    print(ans)

if __name__ == '__main__':
    solve()