SPOJ in Gyumri

   У Коли много друзей. Он часто ходит к ним домой играть,бывает, что он приходит к одному своему другу, а потом от него идёт к другому, а от этого к третьему и т.д. Чтобы не опаздывать он придумал мини-карту. Он пронумеровал дома всех своих  N друзей числами от 1 до N. Коля используем M тропинок, чтобы переходить от одного друга к другому. Тропинки характеризуются тремя числами X, Y, Z, где X, Y - номера домов друзей, которых связывает тропинка, а Z - её длина. Между двумя домами может быть несколько тропинок разной длины. По тропинке можно ходить в обе стороны. Мини-карта представляет собой квадратную матрицу A размером N*N, где Aij - длина кратчайшего пути между i-ым и j-ым домами (возможно проходя через другие дома). Aii всегда равен 0. Если из i-ого дома нельзя добраться до j-ого, то Aij = -1. Помогите Коле составить эту мини-карту.

Входные данные.

   Первая строка содержит 2 числа N и M (2 ≤ N ≤ 100, 1 ≤ M ≤ 300) - соответственно число друзей и тропинок. Далее следует M строк по 3 числа в каждой Xi Yi Zi (1 ≤ Zi ≤ 100) - описание i-ой тропинки, где X, Y - номера домов друзей, которых связывает тропинка, а Z - её длина.

Выходные данные.

   N строк по N чисел в каждой - мини-карта.

Пример.