무방향 가중치 그래프(Undirected Weighted Graph)는 정점(Vertex)들과 두 정점을 잇는 방향성이 없는 간선(Edge)들에 비용(가중치)이 부여된 자료구조입니다.

그래프를 컴퓨터에서 표현하는 대표적인 방법 중 하나는 인접 리스트(Adjacency List)입니다.

인접 리스트는 각 정점마다 해당 정점과 직접 연결된 정점들과 가중치 정보를 리스트로 관리하는 방식입니다.

\(V\)개의 정점과 \(E\)개의 가중치 간선 정보가 주어졌을 때, 이 그래프를 인접 리스트 형식으로 출력하는 프로그램을 작성하시오.

각 정점 \(i\) (\(1 \le i \le V\))에 대해 출력 형식은 다음과 같아야 합니다.

• i :를 출력한 뒤, \(i\)번 정점과 연결된 간선 정보 \((v, w)\)들을 입력으로 주어진 순서대로 공백으로 구분해 출력합니다.
• 간선 \(u\)와 \(v\)가 주어졌을 때, \(u\)번 정점의 리스트에는 \((v, w)\)가 추가되고 \(v\)번 정점의 리스트에는 \((u, w)\)가 추가됩니다.
• 만약 특정 정점에 연결된 간선이 하나도 없다면, 정점 번호와 콜론(:)까지만 출력하고 줄바꿈합니다.

입력

첫째 줄에 정점의 개수 \(V\)와 간선의 개수 \(E\)가 공백을 사이에 두고 주어진다.

둘째 줄부터 \(E\)개의 줄에 걸쳐 각 간선의 양 끝 정점 \(u\), \(v\), 그리고 해당 간선의 가중치 \(w\)가 공백을 사이에 두고 주어진다.

이는 \(u\)와 \(v\) 사이에 가중치 \(w\)인 무방향 간선이 존재함을 의미한다. (서로 다른 두 정점 사이에 둘 이상의 간선은 주어지지 않는다.)

출력

첫째 줄부터 \(V\)개의 줄에 걸쳐 1번 정점부터 \(V\)번 정점까지의 인접 리스트 상태를 형식에 맞춰 출력한다.

각 연결 정보는 입력받은 순서 그대로 \((v, w)\) 형식으로 공백을 두고 출력해야 한다.

제한사항

• \(1 \le V \le 100,000\)
• \(0 \le E \le 300,000\)
• \(1 \le u, v \le V\) (\(u \ne v\), 자기 자신으로 향하는 간선은 없다.)
• 간선의 가중치 \(w\)는 \(1 \le w \le 1,000,000\) 인 정수이다.

예제 입력 1

4 4
1 3 5
1 2 10
3 4 7
4 1 2

예제 출력 1

1 : (3, 5) (2, 10) (4, 2)
2 : (1, 10)
3 : (1, 5) (4, 7)
4 : (3, 7) (1, 2)

예제 입력 2

5 3
1 4 20
4 5 15
1 5 8

예제 출력 2

1 : (4, 20) (5, 8)
2 :
3 :
4 : (1, 20) (5, 15)
5 : (4, 15) (1, 8)