※ 구글 번역기에 돌린 걸 Fine-tuning했습니다. 번역이 어색할 수 있으나, 문제를 푸는 데는 지장이 없습니다.
문제
변장의 달인인 오딘은 종종 다양한 모습으로 변장한 채로 사람들과 만나곤 합니다. 오딘이 가장 자주 하는 변장은 푸른 망토와 펠트 모자를 쓴 노인의 모습으로, 창을 든 까마귀 두 마리나 늑대 두 마리와 함께 있는 경우가 많습니다. 사람들은 오딘이 가난한 방랑자나 못생긴 난쟁이의 모습으로 세상을 떠돌아다닌다고 믿으며, 모습만 보고 환대를 하지 않거나 쫓아내는 자에게는 재앙이 찾아온다고 믿었습니다. 스칸디나비아 사람들은 오딘이 종종 말을 타고 땅을 횡단하거나, 사람들의 눈에 띄지 않은 채로 전투에 참여해서 합당한 측이 승리하도록 도왔다고 믿곤 합니다.
오딘은 다른 사람과 만날 때면 다양한 이야기를 들려주곤 합니다. 다들 알고 있겠지만, 오딘이 가장 좋아하는 이야기는 프로그래밍 대회에 참가했던 이야기입니다. 오딘이 가장 좋아하는 문제는 다음과 같습니다. 무향 단순 가중치 그래프\*가 주어질 때, $N-1$개의 간선을 선택합니다. 이때, 선택한 간선만을 사용하여 임의의 두 정점 사이를 오갈 수 있어야 하며, 선택한 간선의 가중치 합을 최소화해야 합니다. 오딘은 문제의 답인 선택한 간선의 가중치 합을 출력했습니다.
오딘은 당시 문제에서 주어진 그래프의 정점이 $N$개이고 간선이 $M$개였으며, 간선의 가중치는 $R$ 이하의 양의 정수임을 기억하고 있습니다. 또한 문제의 답이 $S$였음을 기억하고 있습니다. 하지만 문제에서 주어진 그래프를 기억하지 못하고 있습니다. 오딘을 도와 오딘이 기억하고 있는 부분을 모두 만족하는 그래프를 만들거나, 그러한 그래프가 없음을 보이세요.
\* 무향 단순 가중치 그래프란, 간선에 가중치가 있고 방향이 없으며, 두 정점을 직접 연결하는 간선이 최대 1개이며 양 끝점이 같은 간선은 없는 그래프를 의미합니다.
입력
첫째 줄에 $4$개의 정수 $N$, $M$, $S$, $R$이 주어집니다. $(1 \le N \le 10^5;$ $1 \le M \le 10^5;$ $1 \le R \le 10^4;$ $|S| \le 10^9)$
출력
만약 조건을 만족하는 그래프가 존재하지 않는다면 -1을 출력합니다.
만약 조건을 만족하는 그래프가 존재한다면, $M$개의 줄에 걸쳐 그래프의 정보를 출력합니다. 각 줄에는 $3$개의 정수 $U$, $V$, $W$를 공백으로 구분하여 출력하며, 이는 두 정점 $U$와 $V$를 잇는 가중치 $W$의 간선을 의미합니다.
hibye1217 1년 전 1
※ 구글 번역기에 돌린 걸 Fine-tuning했습니다. 번역이 어색할 수 있으나, 문제를 푸는 데는 지장이 없습니다.
문제
변장의 달인인 오딘은 종종 다양한 모습으로 변장한 채로 사람들과 만나곤 합니다. 오딘이 가장 자주 하는 변장은 푸른 망토와 펠트 모자를 쓴 노인의 모습으로, 창을 든 까마귀 두 마리나 늑대 두 마리와 함께 있는 경우가 많습니다. 사람들은 오딘이 가난한 방랑자나 못생긴 난쟁이의 모습으로 세상을 떠돌아다닌다고 믿으며, 모습만 보고 환대를 하지 않거나 쫓아내는 자에게는 재앙이 찾아온다고 믿었습니다. 스칸디나비아 사람들은 오딘이 종종 말을 타고 땅을 횡단하거나, 사람들의 눈에 띄지 않은 채로 전투에 참여해서 합당한 측이 승리하도록 도왔다고 믿곤 합니다.
오딘은 다른 사람과 만날 때면 다양한 이야기를 들려주곤 합니다. 다들 알고 있겠지만, 오딘이 가장 좋아하는 이야기는 프로그래밍 대회에 참가했던 이야기입니다. 오딘이 가장 좋아하는 문제는 다음과 같습니다. 무향 단순 가중치 그래프\*가 주어질 때, $N-1$개의 간선을 선택합니다. 이때, 선택한 간선만을 사용하여 임의의 두 정점 사이를 오갈 수 있어야 하며, 선택한 간선의 가중치 합을 최소화해야 합니다. 오딘은 문제의 답인 선택한 간선의 가중치 합을 출력했습니다.
오딘은 당시 문제에서 주어진 그래프의 정점이 $N$개이고 간선이 $M$개였으며, 간선의 가중치는 $R$ 이하의 양의 정수임을 기억하고 있습니다. 또한 문제의 답이 $S$였음을 기억하고 있습니다. 하지만 문제에서 주어진 그래프를 기억하지 못하고 있습니다. 오딘을 도와 오딘이 기억하고 있는 부분을 모두 만족하는 그래프를 만들거나, 그러한 그래프가 없음을 보이세요.
\* 무향 단순 가중치 그래프란, 간선에 가중치가 있고 방향이 없으며, 두 정점을 직접 연결하는 간선이 최대 1개이며 양 끝점이 같은 간선은 없는 그래프를 의미합니다.
입력
첫째 줄에 $4$개의 정수 $N$, $M$, $S$, $R$이 주어집니다. $(1 \le N \le 10^5;$ $1 \le M \le 10^5;$ $1 \le R \le 10^4;$ $|S| \le 10^9)$
출력
만약 조건을 만족하는 그래프가 존재하지 않는다면
-1을 출력합니다.만약 조건을 만족하는 그래프가 존재한다면, $M$개의 줄에 걸쳐 그래프의 정보를 출력합니다. 각 줄에는 $3$개의 정수 $U$, $V$, $W$를 공백으로 구분하여 출력하며, 이는 두 정점 $U$와 $V$를 잇는 가중치 $W$의 간선을 의미합니다.