CodeEff/ECCO huggingface dataset:
# Original solution
import math
N = int(eval(input()))

t = 0
a = 0
for i in range(N):
    T, A = list(map(int, input().split()))
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= T
            sum_a -= A
            if sum_t < t or sum_a < a:
                sum_t += T
                sum_a += A
                break
        t = sum_t
        a = sum_a
        continue

print((t + a))


# Optimized solution
import math
N = int(eval(input()))

t = 0
a = 0
for i in range(N):
    T, A = list(map(int, input().split()))
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        # while True:
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        # if sum_t < t or sum_a < a:
        #     sum_t += T
        #     sum_a += A
        #     break
        t = sum_t
        a = sum_a
        continue

print((t + a))
# Original solution
N = int(eval(input()))
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = list(map(int, input().split()))
ans = T[0]+A[0]

for i in range(N-1):
    for j in range(10**18):
        if (ans+j)%(T[i+1]+A[i+1])==0 and (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
               ans += j
               break

print(ans)


# Optimized solution
N = int(eval(input()))
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = list(map(int, input().split()))
t = a = 1
for i in range(N):
    n = max(-(-t//T[i]), -(-a//A[i]))
    t = n*T[i]
    a = n*A[i]
print((t+a))
# Original solution
n = int(eval(input()))
ary = list(map(int, input().split()))
for i in range(n - 1):
  tmp_ary = list(map(int, input().split()))
  t_rate = (ary[0] - 1) // tmp_ary[0] + 1
  a_rate = (ary[1] - 1) // tmp_ary[1] + 1
  rate = max([t_rate, a_rate])
  ary = list([x * rate for x in tmp_ary])
print((int(ary[0] + ary[1])))

# Optimized solution
n = int(eval(input()))
ary = list(map(int, input().split()))
for i in range(n - 1):
  tmp_ary = list(map(int, input().split()))
  # 桁が大きいとceil, floorでは正しく判定ができない
  t_rate = (ary[0] - 1) // tmp_ary[0] + 1
  a_rate = (ary[1] - 1) // tmp_ary[1] + 1
  rate = max([t_rate, a_rate])
  ary = list([x * rate for x in tmp_ary])
print((int(ary[0] + ary[1])))
# Original solution
N = int(eval(input()))
TA = [list(map(int, input().split())) for i in range(N)]

x = 0
y = 0
for t, a in TA:
    if x <= t and y <= a:
        x = t
        y = a
    else:
        if t >= a:
            while(1):
                if (x*a) % t == 0 and (x*a) // t >= y:
                    y = (x*a) // t
                    break
                else:
                    x += 1
        else:
            while(1):
                if (y*t) % a == 0 and (y*t) // a >= x:
                    x = (y*t) // a
                    break
                else:
                    y += 1

print((x+y))


# Optimized solution
import math
N = int(eval(input()))
TA = [list(map(int, input().split())) for i in range(N)]

x = 1
y = 1
for t, a in TA:
    if x <= t and y <= a:
        x = t
        y = a
    else:
        v = max(-(-x//t), -(-y//a))
        x = v * t
        y = v * a


print((x+y))
# Original solution
n = int(eval(input()))
l = [input().split() for _ in range(n)]
ans = [0,0]
for i in range(n):
    ref_1 = int(l[i][0])
    ref_2 = int(l[i][1])
    for j in range(2,10**18-1):
        if (ans[0]>ref_1) or (ans[1]>ref_2):
            ref_1 = int(l[i][0])
            ref_2 = int(l[i][1])
            ref_1 *= j
            ref_2 *= j
        else:
            break

    ans[0], ans[1] = ref_1, ref_2
print((sum(ans)))

# Optimized solution
n = int(eval(input()))
A, B = 0, 0
for i in range(n):
    x, y = list(map(int,input().split()))
    dx, dy = 1, 1
    if A > x:
        dx = A // x
        if A % x != 0:
            dx += 1
    
    if B > y:
        dy = B // y
        if B % y != 0:
            dy += 1

    a = max(dx, dy)
    A, B = a * x, a * y
print((A + B))
# Original solution
N = int(eval(input()))

# initial
p_t, p_a = 1, 1

for i in range(N) :
    t, a = list(map(int, input().split()))
    t_up, a_up = t, a
    
    if t >= p_t and a >= p_a : 
        p_t, p_a = t, a
    else :
        while t_up < p_t or a_up < p_a :
            t_up += t
            a_up += a
            # print("DBG2 : ", t, a)
            
        p_t, p_a = t_up, a_up
        
    # print(p_t, p_a)

print((p_t + p_a))
    
    
    
    

# Optimized solution
N = int(eval(input()))

# initial
p_t, p_a = 1, 1

for i in range(N) :
    t, a = list(map(int, input().split()))
    t_up, a_up = t, a
    
    if t >= p_t and a >= p_a : 
        p_t, p_a = t, a
    else :
        f = max(
            p_t // t if p_t % t == 0 else p_t // t + 1,  
            p_a // a if p_a % a == 0 else p_a // a + 1
        )
        
        p_t, p_a = t*f, a*f

print((p_t + p_a))
# Original solution
N = int(eval(input()))
TA = [list(map(int, input().split())) for i in range(N)]

t = 1
a = 1

for i in range(N):
    T, A = TA[i]
    mul = 2
    while t > T or a > A:
        T = TA[i][0] * mul
        A = TA[i][1] * mul
        mul += 1
    t = T
    a = A
print((t+a))

# Optimized solution
N = int(eval(input()))
TA = [list(map(int, input().split())) for i in range(N)]

t = 1
a = 1

for i in range(N):
    T, A = TA[i]
    if t > T or a > A:
        tmul = (t+T-1) // T
        amul = (a+A-1) // A
        mul = max(tmul, amul)
        T *= mul
        A *= mul
    t = T
    a = A
print((t+a))
# Original solution
N = int(eval(input()))
A = []
B = []
for i in range(N) :
    in_a,in_b = list(map(int,input().split()))
    A.append(in_a)
    B.append(in_b)
    
for i in range(1,N) :
    a = A[i]
    b = B[i]
    while ((A[i-1] > a) or (B[i-1] > b)) :
        a += A[i]
        b += B[i]
    A[i] = a
    B[i] = b
ans = A[-1] + B[-1]
print(ans)


# Optimized solution
N = int(eval(input()))
A = []
B = []
for i in range(N) :
    in_a,in_b = list(map(int,input().split()))
    A.append(in_a)
    B.append(in_b)
    
for i in range(1,N) :
    if A[i-1] > A[i] :
        if A[i-1] % A[i] == 0 :
            a = A[i-1]//A[i]
        else :
            a = A[i-1]//A[i] + 1
    else :
        a = 1
    
    if B[i-1] > B[i] :
        if B[i-1] % B[i] == 0 :
            b = B[i-1]//B[i]
        else :
            b = B[i-1]//B[i] + 1
    else :
        b = 1
    
    p = max(a,b)
    
    A[i] *= p
    B[i] *= p

ans = A[-1] + B[-1]

print(ans)
# Original solution
import math
from decimal import *

n = int(eval(input()))
l = [[int(i) for i in input().split()] for j in range(n)]

def newT(t, ratio):
    a = Decimal(t[0]) / Decimal(ratio[0])
    b = Decimal(t[1]) / Decimal(ratio[1])
    if a <= 1 and b <= 1:
        return ratio
    else:
        c = math.ceil(max([a, b]))
        return [i*c for i in ratio]

to = l[0]
for li in l[1:]:
    to = newT(to, li)

print((to[0]+to[1]))


# Optimized solution
import math
from decimal import *

n = int(eval(input()))
l = [[int(i) for i in input().split()] for j in range(n)]

def newT(t, ratio):
    if t[0] <= ratio[0] and t[1] <= ratio[1]:
        return ratio
    else:
        #切り上げ (x+p-1)//p
        c = max((t[0]+ratio[0]-1)//ratio[0], (t[1]+ratio[1]-1)//ratio[1])
        return [i*c for i in ratio]

to = l[0]
for li in l[1:]:
    to = newT(to, li)

print((to[0]+to[1]))
# Original solution
# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

# 比がa:bとなる合計最小の票分布はa,b
# 次にc:dになったとき、a<=cかつb<=dを満たすまでc,dを2倍、3倍、と増やしていく

N = int(eval(input()))
TA = [list(map(int, input().split())) for _ in range(N)]

a, b = TA[0]
ans = a + b

for idx in range(1,N):
    c, d = TA[idx]
    ori_c, ori_d = c, d
    while c < a or d < b:
        c += ori_c
        d += ori_d
    ans = c+d
    a,b = c,d
    
print(ans)

# Optimized solution
# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

# 比がa:bとなる合計最小の票分布はa,b
# 次にc:dになったとき、a<=cかつb<=dとなるようにc,dに同じ数をかける

import math

N = int(eval(input()))
TA = [list(map(int, input().split())) for _ in range(N)]

a, b = TA[0]
c, d = a, b

for idx in range(1,N):
    c, d = TA[idx]
    multi = max((a+c-1)//c, (b+d-1)//d)
    c *= multi
    d *= multi
    a,b = c,d
    
print((c+d))
# Original solution
n=int(eval(input()))
a,b=list(map(int,input().split()))
if n!=1:
	for _ in range(n-1):
		A,B=list(map(int,input().split()))
		c=0
		d=0
		k=1
		while a>c or b>d:
			c=k*A
			d=k*B
			k+=1
		a=c
		b=d
print((a+b))

# Optimized solution
n=int(eval(input()))
a,b=list(map(int,input().split()))
if n!=1:
	for _ in range(n-1):
		A,B=list(map(int,input().split()))
		k=max(1,(a+A-1)//A,(b+B-1)//B)
		a=k*A
		b=k*B
print((a+b))
# Original solution
n = int(eval(input()))

tkhs = 1
aoki = 1

for _ in range(n):
    t, a = list(map(int, input().split()))
    k = 1
    while not(tkhs <= k*t and aoki <= k*a):
        k += 1
    tkhs = k*t
    aoki = k*a

print((tkhs+aoki))


# Optimized solution
n = int(eval(input()))
from math import ceil

tkhs = 1
aoki = 1

for _ in range(n):
    t, a = list(map(int, input().split()))
    k = max((tkhs+t-1)//t, (aoki+a-1)//a)
    tkhs = k*t
    aoki = k*a

print((tkhs+aoki))
# Original solution
from math import *
from decimal import * 
N = int(eval(input()))
T = []
A = []
for i in range(0, N):
    ti, ai = [Decimal(int(x)) for x in input().split()]
    T.append(ti)
    A.append(ai)

prevT = T[0]
prevA = A[0]
for i in range(1, N):
    nextfacT = int(ceil(prevT / T[i]))
    nextfacA = int(ceil(prevA / A[i]))
    nextfac = max(nextfacT, nextfacA)
    prevT = nextfac * T[i]
    prevA = nextfac * A[i]

print((prevA+prevT))


# Optimized solution
from math import *
N = int(eval(input()))
T = []
A = []
for i in range(0, N):
    ti, ai = [int(x) for x in input().split()]
    T.append(ti)
    A.append(ai)

prevT = T[0]
prevA = A[0]
for i in range(1, N):
    nextfacT = int(ceil((prevT + T[i] - 1) // T[i]))
    nextfacA = int(ceil((prevA + A[i] - 1) // A[i]))
    nextfac = max(nextfacT, nextfacA)
    prevT = nextfac * T[i]
    prevA = nextfac * A[i]

print((prevA+prevT))
# Original solution
n = int(eval(input()))
tvote = 1
avote = 1

for i in range(n):
	t, a = [int(n) for n in input().split()]
	num = 1
	while True:
		tnow = num*t
		anow = num*a
		if tnow >= tvote and anow >= avote:
			tvote = tnow
			avote = anow
			break
		num += 1
	
print((tvote+avote))




# Optimized solution
n = int(eval(input()))
tvote = 1
avote = 1

for i in range(n):
	t, a = [int(n) for n in input().split()]
	k = (tvote-1)//t + 1
	tnow = t * k
	anow = a * k
	if avote > anow:
		k = (avote-1)//a + 1
		tnow = t * k
		anow = a * k
	tvote = tnow
	avote = anow
	
print((avote+tvote))
# Original solution
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
N=int(eval(input()))
x,y=0,0
for i in range(N):
  p=0
  T,A=list(map(int,input().split()))
  if i==0:
    x,y=T,A
    continue
  if x<=T and y<=A:
    x,y=T,A
  elif x<=T and A<y:
    if y%A!=0:
      p=1
    x=T*(y//A+p)
    y=A*(y//A+p)
  elif T<x and y<=T:
    if x%T!=0:
      p=1
    y=A*(x//T+p)
    x=T*(x//T+p)
  else:
    if (x//T+1)<=(y//A+1):
      if y%A!=0:
        p=1
      x=T*(y//A+p)
      y=A*(y//A+p)
    else:
      if x%T!=0:
        p=1
      y=A*(x//T+p)
      x=T*(x//T+p)
print((x+y))

# Optimized solution
N=int(eval(input()))
x,y=0,0
for i in range(N):
  p=0
  T,A=list(map(int,input().split()))
  if i==0:
    x,y=T,A
    continue
  if x<=T and y<=A:
    x,y=T,A
  elif x<=T and A<y:
    if y%A!=0:
      p=1
    x=T*(y//A+p)
    y=A*(y//A+p)
  elif T<x and y<=T:
    if x%T!=0:
      p=1
    y=A*(x//T+p)
    x=T*(x//T+p)
  else:
    if (x//T+1)<=(y//A+1):
      if y%A!=0:
        p=1
      x=T*(y//A+p)
      y=A*(y//A+p)
    else:
      if x%T!=0:
        p=1
      y=A*(x//T+p)
      x=T*(x//T+p)
print((x+y))
# Original solution
import fractions
N=int(eval(input()))
T,A=list(map(int,input().split()))
for i in range(1,N):
    nT,nA=list(map(int,input().split()))
    m,p=nT,nA
    while(nT<T or nA<A):
        nT+=m;nA+=p
    T,A=nT,nA
print((T+A))

# Optimized solution
import fractions
N=int(eval(input()))
T,A=list(map(int,input().split()))
for i in range(1,N):
    nT,nA=list(map(int,input().split()))
    if(nT>=T and nA>=A):
        T,A=nT,nA
        continue
    pT,pA=T//nT,A//nA
    if(T%nT!=0):
        pT+=1
    if(A%nA!=0):
        pA+=1
    T,A=nT*max(pT,pA),nA*max(pT,pA)
print((T+A))
# Original solution
n = int(eval(input()))
ratio_array = [tuple(map(int, input().split())) for _ in range(n)]

votes_numｓ = (1, 1)

for x, y in ratio_array:
    t, a = votes_numｓ
    m = max((t+x-1)//x, (a+y-1)//y)
    votes_numｓ = (m*x, m*y)

print((sum(votes_numｓ)))

# Optimized solution
n = int(eval(input()))
ratio_array = [tuple(map(int, input().split())) for _ in range(n)]

t, a = 1, 1

for x, y in ratio_array:
    m = max((t+x-1)//x, (a+y-1)//y)
    t, a = m*x, m*y

print((t + a))
# Original solution
n = int(eval(input()))
t,a = list(map(int,input().split()))
for i in range(n-1):
  T,A=list(map(int,input().split()))
  count = 0
  while (A*count < a) or (T*count < t):
    count += 1
  a = count * A
  t = count * T
print((a+t))

# Optimized solution
n = int(eval(input()))
t,a = list(map(int,input().split()))
for i in range(n-1):
  T,A=list(map(int,input().split()))
  count = max(a//A,t//T)
  while (A*count < a) or (T*count < t):
    count += 1
  a = count * A
  t = count * T
print((a+t))
# Original solution
n=int(eval(input()))
ta=[list(map(int, input().split())) for _ in range(n)]
a,b=0,0
for i in range(n):
    x,y=ta[i]
    j,k=x,y
    t=0
    while(1):
        t+=1
        if j*t>=a and k*t>=b:
            break
    a,b=j*t,k*t
print((a+b))

# Optimized solution
n=int(eval(input()))
ta=[list(map(int, input().split())) for _ in range(n)]
a,b=1,1
import math
for i in range(n):
    x,y=ta[i]
    t=max(-(-a//x),-(-b//y))
    a,b=t*x,t*y
print((a+b))
# Original solution
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: "List[int]", A: "List[int]"):

    a0, a1 = T[0], A[0]
    for t, a in zip(T, A):
        while a0*a != a1*t:
            if a0/a1 - t/a > 0:
                a1 += 1
            else:
                a0 += 1
        # print(a0, a1)
    print((a0+a1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = [int()] * (N)  # type: "List[int]"
    A = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        T[i] = int(next(tokens))
        A[i] = int(next(tokens))
    solve(N, T, A)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    # i回目 Ti : Ai
    N = int(eval(input()))
    T, A = [], []
    for i in range(N):
        t, a = list(map(int, input().split()))
        T.append(t)
        A.append(a)

    num = [0, 0]
    for i, (t, a) in enumerate(zip(T, A)):
        # print(i, t, a, num)
        while True:
            if num[0] <= t and num[1] <= a:
                break
            if num[0] <= t:
                # print("B", t, a, num)
                c = -(-num[1]//a)
                a *= c
                t *= c
                continue
            if num[1] <= a:
                # print("C", t, a, num)
                c = -(-num[0]//t)
                199, 17
                a *= c
                t *= c
                continue
            c = max(-(-num[0]//t), -(-num[1]//a))
            # print("D", t, a, num, c)
            a *= c
            t *= c
            continue
        num[0] = t
        num[1] = a
        # print(a, t)
    print((num[0]+num[1]))


if __name__ == '__main__':
    main()
# Original solution
def c_AtCoDeer_and_ElectionReport(N, R):
    from math import ceil
    from decimal import Decimal
    t = 1  # 高橋の票数
    a = 1  # 青木の票数
    for x, y in R:
        n = Decimal(max(ceil(t / x), ceil(a / y)))
        t = n * x
        a = n * y
    return t + a

N = int(eval(input()))
R = [[int(i) for i in input().split()] for j in range(N)]
print((c_AtCoDeer_and_ElectionReport(N, R)))

# Optimized solution
def c_atcodeer_and_election_report(N, R):
    t, a = 1, 1  # 高橋, 青木の票数
    for x, y in R:
        # t<=nx ∧ a<=ny を満たす最小のnを求める
        n = max(t // x, a // y)
        if t > n * x or a > n * y:
            n += 1
        t = n * x
        a = n * y
    return t + a

N = int(eval(input()))
R = [[int(i) for i in input().split()] for j in range(N)]
print((c_atcodeer_and_election_report(N, R)))
# Original solution
N = int(eval(input()))
T,A = (int(T) for T in input().split())
for TN in range(1,N):
    TNext,ANext = (int(T) for T in input().split())
    Cnt = 1
    while TNext*Cnt<T or ANext*Cnt<A:
        Cnt += 1
    T = TNext*Cnt
    A = ANext*Cnt
print((A+T))

# Optimized solution
N = int(eval(input()))
TNow,ANow = (int(T) for T in input().split())
for TN in range(1,N):
    TNext,ANext = (int(T) for T in input().split())
    Magn = max(TNow//TNext+(TNow%TNext!=0),ANow//ANext+(ANow%ANext!=0))
    TNow,ANow = TNext*Magn,ANext*Magn
print((TNow+ANow))
# Original solution
N = int(eval(input()))
info = [list(map(int,input().split())) for i in range(N)]
def modify(l1,l2):
    i = 1
    while True:
        if l2[0] * i >= l1[0] and l2[1] * i >= l1[1]:
            l2[0] *= i
            l2[1] *= i
            break
        i += 1
for i in range(N-1):
    modify(info[i],info[i+1])
ans = sum(info[-1])
print(ans)

# Optimized solution
N = int(eval(input()))
info = [list(map(int,input().split())) for i in range(N)]
def modify(l1,l2):
    # k >= b / a
    # a * k >= b
    k1 = l1[0]//l2[0]
    k2 = l1[1]//l2[1]
    k = max(k1,k2)
    for i in range(k,k+2):
        if l2[0] * i >= l1[0] and l2[1] * i >= l1[1]:
            l2[0] *= i
            l2[1] *= i
            break
for i in range(N-1):
    modify(info[i],info[i+1])
ans = sum(info[-1])
print(ans)
# Original solution
n = int(eval(input()))
last_t = 0
last_x = 0
last_y = 0
for i in range(n):
    t, x, y = list(map(int, input().split()))
    if abs(last_x - x) + abs(last_y - y) > t - last_t:
        print("No")
        exit()
    else:
        if (t % 2 == 1 and (x + y) % 2 == 0) or (t % 2 == 0 and (x + y) % 2 == 1):
            print("No")
            exit()
    last_t = t
    last_x = x
    last_y = y
print("Yes")

# Optimized solution
n = int(eval(input()))
T, X, Y = 0, 0, 0
for i in range(n):
    t, x, y = list(map(int, input().split()))
    dxy = abs(X - x) + abs(Y - y)
    dt = t - T
    if dxy > dt or dxy % 2 != dt % 2:
        print("No")
        exit()
print("Yes")
# Original solution
n,m,r=list(map(int,input().split()))
a,b=sorted([n-1,r-m*n])
if a<1:print((0))
else:
 d=1
 for i in range(a):d*=i+1
 u=1
 for i in range(b,a+b):u*=i+1
 print((u//d))


# Optimized solution
n,m,r=list(map(int,input().split()))
r-=n*m
if r<0:print((0))
else:
 from math import*
 print((factorial(n+r-1)//factorial(r)//factorial(n-1)))
# Original solution
n,m,r=list(map(int,input().split()))
r-=m*n
if r<0:print((0))
else:
 a=1
 for i in range(r):a*=i+n
 for i in range(r):a//=i+1
 print(a)


# Optimized solution
n,m,r=list(map(int,input().split()))
r-=m*n
if r<0:print((0))
else:
 d=1
 for i in range(r):d*=i+1
 u=1
 for i in range(r):u*=i+n
 print((u//d))
# Original solution
def fact(a):
    res = 1
    while a:
        res *= a
        a -= 1
    return res

n,m,r = list(map(int,input().split()))
r-=n*m
if r < 0:
    print((0))
else:
    print((fact(r+n-1)//fact(n-1)//fact(r)))

# Optimized solution
def fact(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

def combination(n, k):
    return fact(n)//fact(n-k)//fact(k)

n, m, r = list(map(int, input().split()))

print((combination(r - n*m + n - 1, n-1)))
# Original solution
from collections import deque
import heapq

def dijkstra(s,g):
    color=[0]*n
    dis={}
    for i in range(n):
        dis[i]=float('inf')
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v,cost in g[u]:
            if color[v]!=2:
                if dis[u]+cost<dis[v]:
                    dis[v]=dis[u]+cost
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,m,c=list(map(int,input().split()))
g=[[] for _ in range(n)]
totalcost=0
for i in range(m):
    a,b,d=list(map(int,input().split()))
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g)
dis=sorted(list(dis.items()), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,cost in g[u]:
        if visited[v]==1:
            totalcost-=cost
    ans=min(ans,totalcost+c*x)
print(ans)

# Optimized solution
import heapq

def dijkstra(s,g):
    color=[0]*n
    dis={}
    for i in range(n):
        dis[i]=float('inf')
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v,cost in g[u]:
            if color[v]!=2:
                if dis[u]+cost<dis[v]:
                    dis[v]=dis[u]+cost
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,m,c=list(map(int,input().split()))
g=[[] for _ in range(n)]
totalcost=0
for i in range(m):
    a,b,d=list(map(int,input().split()))
    g[a-1].append([b-1,d])
    g[b-1].append([a-1,d])
    totalcost+=d

pq=[]
dis=dijkstra(0,g)
dis=sorted(list(dis.items()), key=lambda x:x[1])

ans=float('inf')
visited=[0]*n
for u,x in dis:
    visited[u]=1
    for v,cost in g[u]:
        if visited[v]==1:
            totalcost-=cost
    ans=min(ans,totalcost+c*x)
print(ans)
# Original solution
import itertools
from copy import deepcopy

def stuck(Array,Order):
	remain = len(Array)
	if remain == 0: return G(Order),Order
	minG,minOrder = 9999999,[]
	w = sum([int(Array[i][1]) for i in range(remain)])
	for i in range(remain):
		if int(Array[i][2]) >= w-int(Array[i][1]):
			array = deepcopy(Array)
			order = deepcopy(Order)
			order[n-remain] = array.pop(i)
			curG,curOrder = stuck(array,order)
			if curG < minG:
				minG = curG
				minOrder = curOrder
	return minG,minOrder

def G(array):
	nume=sum([(i+1)*int(array[i][1]) for i in range(n)])*1.0
	denomi=sum([int(array[i][1]) for i in range(n)])
	return nume/denomi
	
while 1:
	n=eval(input())
	if n==0:break
	lunch=[input().split() for i in range(n)]
	minG,ans=stuck(lunch,[0]*n)
	for i in range(n):
		print(ans[i][0])

# Optimized solution
def stuck(array):
	order=[]
	while array:
		r = len(array)
		w = sum([array[i][1] for i in range(r)])
		mx = 0
		for i in range(r):
			if array[i][2] >= w-array[i][1] and array[i][1] > mx:
				mx = array[i][1]
				id = i
		order.append(array.pop(id)[0])
	return order

def change(a):
	return a[0],int(a[1]),int(a[2])
	
while 1:
	n = eval(input())
	if n == 0:break
	lunch = [change(input().split()) for i in range(n)]
	ans = stuck(lunch)
	for i in range(n):
		print(ans[i])