from sys import stdin
input = stdin.readline
from heapq import heappush, heappop
from math import gcd
from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

@bootstrap
def dfs(n, p):
    for v, c in G[n]:
        base.append(c*2)
        if v == p: continue
        if dist[v] == -1:
            dist[v] = dist[n]+c
            yield dfs(v, n)
        elif dist[v] < dist[n]:
            res = dist[n]-dist[v]+c
            base.append(res)
    yield

N, M, K = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v, c = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v, c))
    G[v].append((u, c))

dist = [-1]*N
dist[0] = 0
base = []
dfs(0, -1)

def dijkstra(start):
    INF = 10**18
    dist = [INF]*N
    dist[start] = 0
    visited = [False]*N
    que = [(0, start)]
    while que:
        d, now = heappop(que)
        if visited[now]:
            continue
        visited[now] = True
        for next, weight in G[now]:
            if dist[now]+weight < dist[next]:
                dist[next] = dist[now]+weight
                heappush(que, (dist[next], next))
    return dist

dist = dijkstra(0)
GCD = 0
for b in base:
    GCD = gcd(GCD, b)

GCD = gcd(GCD, K)

print(dist[-1]%GCD)