Problem
정보 올림피아드를 준비하기 위해 시장은 도시의 모든 학교에 안정적인 전력 공급을 제공하기로 결정했습니다. 이를 위해서는 대체 전기 "Maibuttya"에서 전력선을 연결해야 합니다. 도시에 있는 학교 중 하나(어느 학교든 상관 없음)에 연결하고 일부 학교를 전력선으로 서로 연결합니다.
학교가 Maibutcha 소스 또는 안정적인 전원 공급 장치가 있는 학교 중 하나에 직접 연결된 경우 안정적인 전원 공급 장치가 있는 것으로 간주됩니다.
일부 학교 쌍 간의 연결 비용이 알려져 있습니다. 시장은 가장 경제적인 두 가지 전력 공급 계획 중 하나를 선택하기로 결정했습니다(계획 비용은 학교 쌍을 연결하는 비용의 합과 같습니다).
학교를 위한 가장 비용 효율적인 대체 전원 공급 장치 두 가지의 비용을 계산하는 프로그램을 작성하세요.
입력
입력 파일의 첫 번째 줄에는 공백으로 구분된 두 개의 자연수인 N(3 <= N <= 100), 도시의 학교 수 M – 그들 사이의 가능한 연결 수. 다음 M 줄 각각에는 Ai, Bi의 세 가지 숫자가 포함되어 있습니다. , Ci, 공백으로 구분, 여기서 Ci - 전력선 배치 비용 (1 <= Ci <= 300) 학교 Ai에서 학교 Bi<까지 /sub > (i=1,2,…,N).
출력
출력 파일의 한 줄에는 로 구분된 두 개의 자연수 S1 및 S2가 포함되어야 합니다. 공백 &ndash ; 두 개의 가장 낮은 회로 비용(S1 <= S2). S1=S2 최소 비용으로 신뢰할 수 있는 전원 공급 장치 체계가 여러 개 있는 경우에만.
입력 데이터에 대해 신뢰할 수 있는 두 가지 전원 공급 방식이 있음을 보장합니다.
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 1 |
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121 |