풀이

1. 각 재료의 양은 정수다. 모든 재료는 비율로 입력이 제시된다는 것을 생각하면, 비율 계산 결과가 실수가 나오면 안된다는 것.
   
   예를들어, A재료의 질량이 10이고, A:B=1:4이면, B는 2.5가 되는데 이는 불가능하다.
   
   그러면, 우리는 기준 질량값을 최소공배수로 선정해야한다는 결론에 도달할 수 있다. 이때, 유클리드 호제법을 활용해서 최소공배수를 계산하자.
   
   최소공배수=(p*q)//최대공약수
   
   p와 q의 최소공배수는 위와 같다.

2. DFS를 활용해서, 각 재료 노드를 방문하며 질량을 갱신해준다. (문제의 입력형태가 a b p q 순으로 a번 재료의 질량 / b번 재료의 질량 = p/q 라서)

def dfs(start):
    visited[start]=True
    for next in graph[start]:
        if not visited[next[0]]: # ex) next : [0,1,1]..[1,3,1]...
            mass[next[0]]=mass[start]*next[2]//next[1]
            dfs(next[0])

3. 이후, 재료의 질량들의 최대공약수로 모든 질량값들을 나눠주면 최소한의 질량으로 구할 수 있다.