import sys
input = sys.stdin.readline

from heapq import heappop,heappush

N,M,C=map(int,input().split())

E=[[] for i in range(N)]

for i in range(M):
    x,y,r,w=map(int,input().split())
    x-=1
    y-=1
    E[x].append((y,r,w))

ANS=[]

for i in range(1,C+1):
    DP=[-1]*N
    DP[0]=i
    Q=[(-i,0)]

    while Q:
        now,ind=heappop(Q)

        now=-now

        for to,r,w in E[ind]:
            if DP[to]<now-(now//r+w):
                DP[to]=now-(now//r+w)
                heappush(Q,(-DP[to],to))

    print(DP[-1])