Informatica Online Judge

  우물 만들기 [2113 / 0841]

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


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

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

Background

$G$국은 중앙정부가 있는 1번 도시에만 우물이 있어 나머지 도시에서 물을 길러가야 한다.

이 국가는 $N$개의 도시가 있으며 모든 도시는 $M$개의 양방향 도로로 이어져 있고, 각 도시마다 거리 $D$가 주어져 있다.

중앙정부는 가장 먼 도시를 찾아 우물을 만들어주고 싶다.

우물을 만들 도시는 $1$번 도시에서 최소 경로로 이동했을 때 가장 먼 거리의 도시이다.
우물을 만들 가장 먼 도시를 찾아보자.

1번 정점과 다른 정점 연결됨을 보장할 수 없으며, 연결되지 않은 간선은 무한으로 취급한다.

Input

첫번째 줄에는 도시 갯수인 $N$, 도로 갯수인 $M$이 공백을 두고 주어진다. ($1<=N,M,D <=10,000$)

$M$줄에 걸쳐서 도로로 연결된 도시 번호와 거리 $D$ 가 공백으로 주어진다.

Output

첫번째 출력값은 가장 먼 거리의 도시 번호를 적는다. 단, 같은 거리의 도시가 여러개이면 도시번호가 가장 작은 번호를 출력한다.

두번째 출력값은 가장 먼 거리의 도시와 같은 거리를 갖는 도시의 갯수를 출력한다.

IO Example

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


출력
3 2

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