30797번 - 가희와 여행가요

가희는 도시 시뮬레이션 게임을 하고 있습니다. 이 게임은 나의 도시와 다른 도시들을 연합하여, 나의 도시를 키우는 게임입니다. 가희의 도시에 사는 사람들은 철도만 이용하여 이동합니다. 건설된 철도 노선들을 적절히 이용하여 가희의 도시에서 도시 $a$로 이동하지 못하면, 사람들은 도시 $a$와 교류를 하지 못하게 되고, 가희의 도시는 도시 $a$와 연합할 수 없습니다.

가희는 월드에 있는 도시 $n-1$개와 가희의 도시를 연합하여 세력을 확장하려고 합니다. 이 게임은 철도 노선 $Q$개를 구매할 수 있습니다. 가희는 이 철도 노선들을 적절하게 구매하여 총 건설 비용을 최소로 하려고 합니다. 그러면서 가희의 도시와 $n-1$개의 도시들을 빠르게 연합하려고 합니다. 가희가 건설할 수 있는 철도 노선들에 대한 정보가 주어졌을 때, 총 건설 비용과 언제 $n-1$개의 도시들과 가희의 도시가 연합하는지 구해주세요. 목표를 달성하는 것이 불가능하다면 첫 줄에 -1을 출력해 주세요.

첫 번째 줄에 $n$과 $Q$가 공백으로 구분되어 주어집니다. 월드에 $1$번 도시부터 $n$번 도시까지 있음을 의미하며, 가희의 도시는 $1$번 도시입니다. 또한 건설할 수 있는 노선은 $Q$개가 있음을 의미합니다.

다음 $Q$개의 줄에 건설할 수 있는 철도 노선의 정보가 아래와 같이 주어집니다.

$from\ to\ cost\ time$

이는 월드에 있는 두 도시, $from$번 도시에서 $to$번 도시를 경유하는 도시 없이, 양방향으로 연결하는 철도를 비용 $cost$를 들여 시각 $time$에 지을 수 있음을 의미합니다. $\left( 1 \le from \le n,1 \le to \le n, from \ne to \right)$ 철도 노선들은 구매하는 즉시 지어지며, 같은 시각에 여러 철도 노선을 건설할 수 있습니다.

가희의 도시와 $n-1$개의 도시가 연합을 하는 시점과 총 건설 비용을 공백으로 구분하여 출력해 주세요. 만약, $n-1$개의 도시와 가희의 도시가 연합할 수 없다면, 첫 줄에 -1을 출력해 주세요.

• $2 \le n \le 2 \cdot 10^5$
• $1 \le Q \le 2 \cdot 10^5$
• $1 \le time \le 10^9$
• $1 \le cost \le 10^9$