모든 도시 쌍 최단 경로 복원

n(1 ≤ n ≤ 100)개의 도시가 있다. 한 도시에서 출발해 다른 도시에 도착하는 버스가 m(1 ≤ m ≤ 100,000)개 있고, 각 버스는 한 번 탈 때마다 정해진 비용이 든다.

모든 도시 쌍 (i, j)에 대해 도시 i에서 도시 j로 가는 최소 비용과 그 비용으로 지나는 경로를 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 n이 주어지고, 둘째 줄에 버스의 개수 m이 주어진다. 셋째 줄부터 m개의 줄에 버스 정보가 한 줄에 하나씩 주어진다. 각 줄에는 버스의 출발 도시 a, 도착 도시 b, 한 번 타는 데 드는 비용 c가 공백으로 구분되어 주어진다. 출발 도시와 도착 도시가 같은 버스는 없고, 같은 도시 쌍을 잇는 버스가 여러 개 있을 수 있다. 비용은 100,000 이하의 자연수이다.

먼저 n개의 줄을 출력한다. i번째 줄의 j번째 수는 도시 i에서 도시 j로 가는 최소 비용이다. 도시 i에서 도시 j로 갈 수 없으면 그 자리에 0을 출력하고, i와 j가 같아도 0을 출력한다.

그 다음 $n \times n$개의 줄을 출력한다. 이 줄들은 i를 1부터 n까지 늘리면서 각 i마다 j를 1부터 n까지 늘린 순서로 도시 쌍 (i, j)에 대응한다. 각 줄에는 도시 i에서 도시 j로 가는 최소 비용 경로에 들어 있는 도시의 개수 k를 먼저 출력하고, 이어서 그 경로에 나오는 도시 번호를 지나는 순서대로 공백으로 구분해 출력한다. 도시 i와 도시 j도 경로에 포함한다. 도시 i에서 도시 j로 갈 수 없거나 i와 j가 같으면 그 줄에는 0만 출력한다.

최소 비용 경로가 여러 개이면 도시 번호를 나열한 수열이 사전순으로 가장 앞서는 경로를 출력한다. 두 수열은 앞에서부터 한 자리씩 비교하고, 한쪽이 다른 쪽의 앞부분과 같으면 더 짧은 쪽이 앞선다.