n, m=[int(s) for s in input().split()]
hypped=dict([[int(s) for s in input().split()] for nr in range(m)])
print(hypped)
edasi=teada={1}
kaik=0
while edasi:
    kaik+=1
    uued={uuritav+kaik for kaik in range(1, 7)  for uuritav in edasi}
    uued={uus for uus in uued if uus not in teada and uus <= n}
    edasi={hypped[uus] if uus in hypped else uus for uus in uued }
    edasi-=teada
    teada.update(edasi)
    teada.update(uued)
    print(kaik, teada, edasi)