Happyland 는 (1 부터 N까지 번호가 번호가 붙여진 ) N개의 마을과 마을들을 연결하는 (1 부터 M까지 번호가 붙여 진) M개의 양방향 도로로 이루어져있다. 1번 마을이 Happyland 의 중심마을이다. 마을의 도로망을 이용하여 1번 마을부터 다른 모든 마을들을 방문할 수 있음이 보장되며 , 모든 도로는 유료도로이다. 도로 i 의 통행료는 ci 센트이며 , 도로의 주인에게 납부하여야 한다 . 최근에 K개의 도로들이 새로 건설되었으며 소유주는 억만장자인 Mr. Greedy 이다 . Mr. Greedy는 새 도로들의 통행료를 결정하여 (통행료가 서로 다를 필요는 필요는 없다 ) 내일 발표하여야 한다 .
두주 후에 Happyland 에서는 대규모 축제가 열릴 예정이다 . 많은 참가자들이 중심마을에 모여서 행진을 할 예정이다. 마을 j 에서는 pj명의 참가자들이 중심마을인 1번 마을로 갈 예정이다. 이 사람들은 여행에 필요한 미리 선정된 도로들만을 이용하여 중심마을로 갈 것이며 , 그 선정된 도로들은 축제 바로 전날 발표가 될 예정이다. 옛 전통에 따라 , 도로 선택은 Happyland 에서 가장 부자인 Mr. Greedy 가 하게 된다 . 또한, 같은 전통에 따라 Mr. Greedy 는 선택된 도로의 통행료의 합이 최소 가 되도록 도로들을 선택해야 하고 , 누구나 마을 j 에서 마을 1까지의 도로들을 이용할 수 있어야 있어야 한다 (그러므로 , 통행료가 에지 (도로 )의 가중 치라면 선택된 에지들은 “최소비용신장트리 ”를 구성하게 된다 ). 만약 그러한 에지들의 집합이 여러 개가 있다면 , Mr. Greedy 는 그 중하나를 선택할 선택할 수 있다 .
Mr . Greedy 는 그가 건설한 K개의 새로운 도로로부터 얻을 수 있는 수입이 단순히 통행료에만 달려있지 않다는 것을 잘 알고 있다 . 통행료 수입은 그 도로를 여행한 사람들이 지불한 통행료의 합이다 . 보다 자세히 말하자면 , 만약 p 명의 사람들이 도로 i 를 지나간다면 , 도로 i 로부터 얻는 수입은 ci*p 가 된다 . 옛날 도로들은 Mr. Greedy 의 소유가 아니므로 , Mr. Greedy 는 새로 건설한 도로로부터만 통행료를 거둘 수 있다 . Mr. Greedyedy 는 엉큼한 엉큼한 계획을 가지고 있다 . 그는 도로 선택을 통해 축제기간 동안 거기서 얻는 통행료 수입을 최대화 하려고 하려고 한다 . 그는 새로운 도로의 통행료를 정하고 (내일 발표해야 하는 ) 축제 때 그 도로를 도로를 선택하여 (축제 하루 전 발표해야 하는 ) , ), K개의 새로운 도로로부터 얻는 수익을 최대화하는 방법을 알기 원한다 . 참고로 , Mr. Greedy 는 전통에 따라 통행료의 합을 최소화하는 도로들을 선택해야만 한다 . 여러분은 기자이며 그의 계획을 폭로하기를 원한다 . 그렇게 하기 위해 , 먼저 Mr. Greedy 가 그의 엉큼한 계획을 통하여 통하여 얼마의 수입을 얻을 수 있는지를 구하는 프로그램을 프로그램을 작성하여야 한다 .
입력 5 5 1 3 5 2 1 2 3 2 3 5 2 4 4 4 3 6 1 3 10 20 30 40 50 출력 400
출처:apio2013