Informatica Online Judge

  전선 끊기 [1236 / 04D4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 62


The Champion of this Problem (C++) : gs15120 - 0ms / 1237byte
My Best Submission (C++) : N/A

[koistudy.net (31st 윤지학)]

Background

지학이는 대단한 부자로, 돈이 많이 들어 있는 금고를 가지고 있습니다.
그런데 어느 날 금고가 망가져서 금고를 해제해야 할 필요성이 생겼습니다.

지학이가 금고를 분해해서 회로를 분석해봤더니, 회로는 N개의 부품과 M개의 전선으로 이루어져 있었습니다.
지학이는 N개의 부품에 1번부터 N번까지 번호를 붙였고, 1번 부품과 N번 부품 간에 전기가 흐를 수 없으면 금고가 해제된다는 것을 알았습니다.

하지만 전선들이 너무 굵어서 끊는 데에는 각각 비용이 필요하고, 이 비용은 서로 다를 수도 있습니다.

전선을 끊어서 1번 부품과 N번 부품 간에 전기가 흐를 수 없도록 하는 최소 비용을 구하세요.

Input

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

다음 M줄에 각 전선에 대한 정보 a_i, b_i, c_i가 주어집니다. ( a_i != b_i )
a_i와 b_i는 각각 전선의 양 끝에 연결된 부품의 번호를 의미하며, c_i는 이 전선을 끊는 데 필요한 비용입니다.

[입력값의 정의역]
2 <= N <= 200
0 <= M <= 1,000
1 <= a_i, b_i <= N
1 <= c_i <= 1,000,000

Output

전선을 끊어서 1번 부품과 N번 부품 간에 전기가 흐를 수 없도록 하는 최소 비용을 출력하세요.

IO Example

입력
4 5
1 2 3
1 3 7
2 3 4
2 4 8
3 4 2

출력
9

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