Ответ:

В матрице строки обозначают город отправления, столбцы — город назначения. Вес дороги записываем в соответствующую ячейку; если дороги нет, ставим 0.

Из города ↓ / В город →1234
1010200
200515
300030
40000