어느 온라인 게임의 데이터 센터는 \(N\)개의 서버 노드와 \(M\)개의 양방향 회선으로 연결되어 있다. 각 회선은 두 노드를 잇고, 패킷이 그 회선을 지날 때 \(w\)만큼의 지연(ms)이 발생한다.

플레이어 노드 \(S\)에서 매치 서버 노드 \(T\)까지 패킷을 보내려 한다. 기준은 다음과 같다.

1. 총 지연이 최소인 경로를 택한다.
2. 총 지연이 같은 경로가 여러 개라면, 그중 지나는 회선의 개수가 최소인 경로를 택한다.

이 두 기준에 따른 최소 총 지연과 그때의 회선 개수를 출력하여라. \(S\)에서 \(T\)로 갈 수 없으면 \(-1\)만 출력한다.

다중 회선이 존재할 수 있으며, 자기 루프는 없다.

• \(2 \le N \le 20{,}000\)
• \(1 \le M \le 100{,}000\)
• \(1 \le u, v \le N\), \(u \ne v\)
• \(1 \le w \le 10{,}000\)
• \(1 \le S, T \le N\), \(S \ne T\)

첫째 줄에 \(N\ M\ S\ T\)가 주어진다.

다음 \(M\)개의 줄에 각 회선의 정보 \(u\ v\ w\)가 주어진다.

\(S\)에서 \(T\)까지 도달 가능하면 최소 총 지연 회선 개수를 공백으로 구분하여 한 줄에 출력한다. 도달할 수 없으면 \(-1\)을 출력한다.

riseoj 작성

출처 Original