가희와 여행가요

가희는 도시 시뮬레이션 게임을 하고 있습니다. 이 게임에서는 가희의 도시를 세계의 다른 도시들과 연합시켜 도시를 키웁니다. 가희의 도시에 사는 사람들은 철도로만 이동합니다. 건설된 철도 노선을 적절히 이용해서 가희의 도시에서 도시 $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$에 지을 수 있다는 뜻입니다. $(1 \le from \le n, 1 \le to \le n, from \ne to)$ 철도 노선은 구매하는 즉시 지어지며, 같은 시각에 여러 철도 노선을 건설할 수 있습니다.

가희의 도시가 $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$