matriz array java

Percorri uma matriz e achei um números de cidades vizinhas. Estou imprimindo toda vez que acho. Porém ele ao percorrer a matriz, encontra os caminho das cidade 1-2-3-4 e depois o caminho da 2-3, mas este eu já tenho pois está contido na 1-2-3-4. Como faço pra não imprimir este segundo caminho?

minha saída está assim
1 2 3 6 8
3 5 9
3 8