아이스크림
시간 제한1초메모리 제한512 MB
초콜릿 공급점과 바닐라 공급점, 혼합 지점이 있는 용량 있는 배관망이 주어질 때, 두 종류가 같은 양으로 섞이는 최대 분당 생산량을 구한다.
문제
BGO(Better Get Obese) 아이스크림 공장은 연말 성수기를 준비하고 있다. 몇 년 동안 판매가 부진했던 공장은 가장 인기 있는 제품인 초콜릿과 바닐라 맛 아이스크림에만 집중하기로 했다.
이런 아이스크림을 완벽하게 만들려면 혼합기에 바닐라 아이스크림과 초콜릿 아이스크림이 같은 양씩 들어가야 한다.
공장에는 초콜릿 아이스크림과 바닐라 아이스크림을 각각 만드는 두 대의 크림 제조기가 있고, 만들어진 아이스크림은 두 개의 탱크에 따로 저장된다. 여기에서 파이프를 통해 혼합기로 보낼 수 있는데, 파이프의 지름에 따라 1분에 지나갈 수 있는 아이스크림의 양의 상한이 정해진다. 파이프들은 용접점에서 만나며, 이곳에서 아이스크림의 흐름이 한 파이프에서 다른 파이프로 이동한다. 세 개 이상의 파이프가 만나는 용접점에서는 흐름이 합쳐지거나 여러 흐름으로 나뉠 수도 있다. 어차피 나중에 섞이므로 운반 중에 두 맛을 분리해 둘 필요는 없다.
파이프 시스템의 지도가 주어졌을 때, 공장이 1분에 몇 리터의 아이스크림을 생산할 수 있는지 구할 수 있는가?
입력
첫째 줄에는 용접점의 수 n (3 ≤ n ≤ 200)과 파이프의 수 m (2 ≤ m ≤ 1 000)이 주어진다. 둘째 줄에는 서로 다른 세 정수 f, c, v (1 ≤ f, c, v ≤ n)가 주어지며, 이는 각각 혼합기, 초콜릿 탱크, 바닐라 탱크가 파이프 시스템에 연결된 용접점이다.
이어서 m개의 줄이 주어지고, i번째 줄에는 세 개의 음이 아닌 정수 ui, vi, xi (1 ≤ ui, vi ≤ n, 1 ≤ xi ≤ 1 000)가 주어진다. 이는 용접점 ui와 vi 사이에 1분에 xi리터의 아이스크림을 운반할 수 있는 파이프가 있다는 뜻이다. 같은 두 용접점 사이에 여러 파이프가 나란히 놓일 수 있다.
출력
BGO 공장이 1분에 생산할 수 있는 아이스크림의 최대 양(리터)을 정수 하나로 출력한다.