Time Limit: 1s
Memory Limit: 128MB
WithCS 농장에 비가 올때마다 연못이 넘쳐 주인 아주머니의 꽃밭으로 물이 흘러가 버립니다. 한마디로 꽃밭은 엉망진창이 되버리고, 아주머니는 분노하고, 주인 아저씨는 서러움에 눈물이 흐르게 됩니다. 그래서 주인 아저씨는 자신이 가진 공학적인 지식을 총 동원해서 아주머니의 꽃밭에 물이 흐르지 않도록 도랑을 설계하였습니다! 배수로는 연못에서부터 개울가까지 이어지도록 만들었습니다. 주인 아저씨는 사실 대단한 공학자여서, 도랑이 여러갈래로 나뉠 때 보내지는 물의 양을 원하는대로 서로 다르게 하는 제어기를 설치해 놓았습니다.
주인 아저씨는 각각의 도랑이 1분에 몇리터의 물을 보낼 수 있는가에 대한 정보 뿐만 아니라, 도랑의 배치가 어떻게 구성되어있는지를 알고 있습니다. 도랑은 서로 연결되어 망(network)의 형태로 구성됩니다.
모든 정보를 총 동원하여 연못에서 개울가까지 이어진 배수로가 감당할 수 있는 물의 통과량을 계산하십시오. 모든 배수로는 한 방향으로만 흐릅니다. 단, 배수로가 연결되어 원형으로 이어질 수는 있습니다.
* Line 1 : 2개의 정수, N M
- N : (0 <= N <= 200), 도랑의 수
- M : (2 <= M <= 200), 갈림 지점의 수, 1 = 연못, Max(M) = 개울가
* Line 2 ~ N+1 : 3개의 정수, Si Ei Ci
- Si : 도랑의 시작 갈림 지점
- Ei : 도랑의 도착 갈림 지점
- Ci : 도랑이 허용하는 물의 통과량
배수로가 허용하는 물의 통과량의 최대치
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10
50