Doner Time!

면접 대비

시간 제한3초메모리 제한2048 MB

요약
가중 무방향 그래프에서 교차로 1로부터 가장 가까운 도네르 가게가 있는 교차로를 찾고, 거리가 같으면 번호가 가장 작은 교차로를 고른다.
난이도

쉬움10점 중 3점

유형
최단 경로, 그래프, 힙
정답자
아직 제출이 없습니다

문제

Every student knows the practice: after having had one too many drinks in the \PUB, you will go to the Doner Shop to treat yourself with some comfort food.

But experience tells you that you and your friends will not recall the way to the Doner Shop when you are drunk. Besides there are a lot of Doner Shops in the city. Therefore you decide to write a program that will tell you how far away the nearest Doner store is from your current location. And tells you with Doner store is closest.

You may assume you can reach at least one Doner Shop from your current location. You always start at the crossing numbered 1.

입력

A line with two integers: N,1<N≤10000N, 1 < N \le 10000, the number of crossings in the city, and S,1<S≤100000S, 1 < S \le 100000, the number of streets in the city.

SS lines with three space seperated integers, a,b,l,1≤a,b≤N,1≤l≤1000a, b, l, 1 \le a, b \le N , 1 \le l \le 1000. Which indicate that a street with length ll connects crossing a with crossing b. All streets are bi-directional.

An integer m,1≤m≤1000m, 1 \le m \le 1000, the number of Doner Shops in the city.

MM lines with one integer c,1≤c≤Nc, 1 \le c \le N which indicates that on crossing cc you can find a Doner shop.

출력

One line with two space separated integers:

CC The number of the crossing at which you can find the closest Doner Shop. If multiple doner stores are equally far away from you, give the one that has the lowest number.

LL The length of the shortest route to the closest Doner Shop.

예제2

  1. 예제 1

    입력
    6 6
1 2 5
1 5 1
5 3 2
2 3 1
2 4 1
3 6 3
2
4
6
    예상 출력
    4 5

  2. 예제 2

    입력
    11 13
1 2 5
2 3 30
2 4 16
4 3 17
2 5 6
5 6 7
6 10 8
10 9 12
8 9 11
8 11 14
7 8 10
1 7 9
5 8 13
3
11
10
3
    예상 출력
    10 26