Здесь вам нужно найти остовное дерево графа, да притом такое, что его можно выпрямить. Но так как, там по сути, как я понял, просто цикл, а ещё есть одно тупиковое ответвление, то вам просто нужно взять и запустить DFS, либо BFS алгоритм с точки, которая около черенка.
Для того, чтобы BFS или DFS сразу не пошли к черенку, удалите ребро ведущую к выходу, то есть тупику, но при этом подразумеваете, что оно есть , это уже и будет то минимальное расстояние, остовное дерево.
Запишите этот путь в массив или множество и задача решена.
Вот DFS, припишите то, что нужно для записи пути и выведите его.
N,M = [int(i) for i in input().split()]
G = {}
for i in V:
if i not in used:
t += 1
dfs(i,G,used)
N, M - количество вершин и ребер соответственно.
Все ребра и вершины необходимо прописать самому.
В данном случае, лучше DFS (поиск в глубину).
Простой
