#include <stdio.h>
#include <string.h>

typedef struct _Edge
{
	int adjvex;
	int seq;
	struct _Edge *next;
} Edge;

typedef struct _Vertex
{
	int seq;
	Edge *link;
} Vertex;

typedef struct _Adjlist
{
	int size;
	Vertex *list;
} Adjlist;

Adjlist *create_Adjlist(int n)
{
	int i;
	Adjlist *adjlist = (Adjlist *)malloc(sizeof(Adjlist));
	adjlist->list = (Vertex *)malloc(n*sizeof(Vertex));

	adjlist->size = n;
	for (i = 0; i < n; i++)
	{
		adjlist->list[i].seq = i;
		adjlist->list[i].link = NULL; // mark the rear
	}
	return adjlist;
}

void insert_Edge(int seq, Vertex *head, int end)
{
	Edge *rear = head->link;
	Edge *newEdge = (Edge *)malloc(sizeof(Edge));
	
	newEdge->seq = seq;
	newEdge->adjvex = end;
	newEdge->next = NULL;
	if (rear == NULL) 
	{ 
		head->link = newEdge; 
	}
	else 
	{
		while (rear->next != NULL) rear = rear->next; // reach the rear
		rear->next = newEdge;						// add the new Edge at the rear
	}
}

void print_Path(int path[])
{
	int i = 0;
	while (path[i + 1] != 0)
		printf("%d ", path[i++]);
	printf("%d\n", path[i]);
}

void DFS(int start, int depth, Adjlist adjlist, int path[], int visited[])
{
	if (start == adjlist.size - 1)
	{
		path[depth] = 0; // mark the end of the path
		print_Path(path);
		return;
	}
	else
	{
		if (!visited[start]) // no loop in a path, thus no vertex should be visited twice
		{
			visited[start] = 1; // if not visited before, now mark it as visited
			Edge *link = adjlist.list[start].link;
			while (link != NULL)
			{
				path[depth] = link->seq; // mark the edge as a step in the path
				DFS(link->adjvex, depth + 1, adjlist, path, visited); // the next start is the vertex the current vertex leads to
				link = link->next; // search the next vertex the current vertex leads to
			}
			visited[start] = 0; // de-visit this vertex so that after quitting other searching can reach this vertex again
			return;
		}
	}
}

void iterate_Path(Adjlist adjlist)
{
	int *path = (int *)malloc(adjlist.size*sizeof(int)); // a path cannot be longer than the number of vertexes
	int *visited = (int *)malloc(adjlist.size*sizeof(int));
	memset(visited, 0, adjlist.size*sizeof(int));  // mark all vertexes as unvisited
	DFS(0, 0, adjlist, path, visited);
	free(path);
	free(visited);
}

int main()
{
	Adjlist *adjlist;
	int n, e;
	int seq,v1,v2,i;

	scanf("%d %d",&n, &e);
	adjlist = create_Adjlist(n);
	for (i = 0; i < e; i++)
	{
		scanf("%d %d %d",&seq,&v1,&v2);
		insert_Edge(seq, &(adjlist->list[v1]), v2);
		insert_Edge(seq, &(adjlist->list[v2]), v1);
	}
	iterate_Path(*adjlist);
	return 0;
}