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

#define nmax 450
#define inf 1<<30
#define nod second
#define cost first
#define pb push_back

using namespace std;

typedef pair <int, int> ii;
int n, m, a, b, da [nmax], db [nmax], pred [nmax];
char f [nmax] [nmax], c [nmax] [nmax];
vector <ii> g [nmax];
vector <int> gf [nmax];
priority_queue <ii, vector <ii>, greater <ii> > q;

void scan ()
{
	int i, x, y, z;
	scanf ("%d%d", &n, &m);
	a=1;
	b=n;
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d%d", &x, &y, &z);
		g [x].pb (ii (z, y));
		g [y].pb (ii (z, x));
	}
}

void dijkstra (int x, int d [])
{
	int i, w;
	for (i=1; i <= n; ++i) d [i]=inf;
	d [x]=0;
	q.push (ii (0, x));
	while (!q.empty ())
	{
		w=q.top().nod;
		if (d [w] < q.top().cost) {q.pop (); continue;}
		q.pop ();
		for (i=0; i != g [w].size (); ++i)
			if (d [g [w] [i].nod] > d [w] + g [w] [i].cost)
			{
				d [g [w] [i].nod] = d [w] + g [w] [i].cost;
				q.push (ii (d [g [w] [i].nod], g [w] [i].nod));
			}
	}
}

void muchii ()
{
	int i, j;
	for (i=1; i <= n; ++i)
		for (j=0; j != g [i].size (); ++j)
			if (da [i] + db [g [i] [j].nod] + g [i] [j].cost == da [b])
			{
				gf [i].pb (g [i] [j].nod);
				gf [g [i] [j].nod].pb (i);
				c [i] [g [i] [j].nod]=1;
				//c [g [i] [j].nod] [i]=0;
				//fprintf (stderr, "%d %d\n", i, g [i] [j].nod);
			}
}

bool bfs ()
{
	int p, u, i, w, q [nmax];
	p=u=1;
	memset (pred, 0, sizeof (pred));
	pred [a]=-1;
	q [p]=a;
	while (p <= u)
	{
		w=q [p];
		++p;
		for (i=0; i != gf [w].size (); ++i)
		{
			if (pred [gf [w] [i]] != 0) continue;
			if (f [w] [gf [w] [i]] >= c [w] [gf [w] [i]]) continue;
			pred [gf [w] [i]]=w;
			if (gf [w] [i] == b) return true;
			q [++u]=gf [w] [i];
		}
	}
	return false;
}

bool flux ()
{
	if (bfs () == false) return false;
	int i;
	for (i=b; i != a; i=pred [i])
	{
		f [pred [i]] [i]++;
		f [i] [pred [i]]--;
	}
	return true;
}

void print (int nod)
{
	int i;
	printf ("%d ", nod);
	for (i=0; i < gf [nod].size (); ++i)
		if (f [nod] [gf [nod] [i]] > 0)
		{
			f [nod] [gf [nod] [i]]=0;
			print (gf [nod] [i]);
			return;
		}
}

int main ()
{
#ifndef ONLINE_JUDGE
	freopen ("185.in", "r", stdin);
	freopen ("185.out", "w", stdout);
#endif
	scan ();
	dijkstra (a, da);
	dijkstra (b, db);
	muchii ();
	if (flux () == false || flux () == false)
	{
		printf ("No solution\n"); return 0;
	}
	print (a);
	printf ("\n");
	print (a);
	printf ("\n");
	return 0;
}