Informatica Online Judge

  영석이 문제 [2143 / 085F]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 0   Total Tried : 3


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs15025]

Background

N개의 노드와 M개의 간선이 주어진다.

간선은 모두 양방향 간선이며, N개의 노드를 이용해 2개의 생성트리를 만든다.

단, 노드 중 두 개가 선택되며 선택된 두 노드는 최종적으로 같은 트리에 있을 수 없다.

두 개의 생성트리를 만드는 데 필요한 최소 비용을 출력하시오.
(단, 하나의 노드만을 원소로 갖는 트리도 생성트리로 취급한다. 만들 수 없을 때에는, -1을 출력한다. )

Input

첫째 줄에는 노드의 수 2<=N<=500과 간선의 수 M이 주어진다.

그 다음 줄부터 0<=M<=10,000줄 동안 간선의 한쪽 끝과 다른 쪽 끝, 간선의 비용이 주어진다.

마지막 줄에는 두 노드 1<=P,Q<=N 가 주어진다.

Output

간선들의 비용의 합을 출력한다. 연결이 불가능할 경우 -1을 출력한다.

IO Example

입력

7 9
1 2 3
1 3 5
2 3 4
3 4 7
4 5 3
5 7 2
3 7 5
1 6 8
6 7 1
2 6

출력

13

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]