#include <iostream>
#include <climits>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define NNODE_MAX 100
#define INFTY INT_MAX
#define NIL (-1)

class Edge {
public:

	int left, right, weight;
	bool hidden;

	Edge( int left, int right, int weight ) : left(left), right(right), weight(weight), hidden(false) {}

	int opp( int n ) { return (left == n)? right : left; }
	void hide() { hidden = true; }
	void restore() { hidden = false; }
	bool visible() const { return !hidden; }

};

int nnode, nedge;
vector<int> G[NNODE_MAX+1];
vector<Edge> E;

int compute( int start, int end, vector<int> &path, int limit ) {
	int D[NNODE_MAX+1], PI[NNODE_MAX+1];

	for ( int u = 1; u <= nnode; u++ ) D[u] = INFTY, PI[u] = NIL;

	multimap<int, int> PQ;
	D[start] = 0, PQ.insert(make_pair(0, start));

	while ( !PQ.empty() ) {
		const int d = PQ.begin()->first;
		const int u = PQ.begin()->second;
		PQ.erase(PQ.begin());

		if ( d >= limit ) return INFTY;
		if ( D[u] < d ) continue;
		if ( u == end ) break;

		for ( int i = 0; i < G[u].size(); i++ ) {
			Edge &e = E[G[u][i]];
			const int v = e.opp(u);
			if ( !e.visible() || e.weight + d >= D[v] ) continue;
			D[v] = e.weight + d;
			PI[v] = u;
			PQ.insert(make_pair(D[v], v));
		}
	}

	if ( D[end] == INFTY ) return INFTY;
	int curr = end;
	while ( curr != NIL )
		path.push_back(curr), curr = PI[curr];
	reverse(path.begin(), path.end());
	return D[end];
}

int main() {
	int A[NNODE_MAX+1][NNODE_MAX+1];

	while ( cin >> nnode >> nedge, nnode != -1 ) {
		for ( int u = 1; u <= nnode; u++ ) G[u].clear();
		E.clear();

		for ( int u = 1; u <= nnode; u++ )
			for ( int v = 1; v <= nnode; v++ ) A[u][v] = INFTY;

		int left, right, weight;
		for ( int i = 0; i < nedge; i++ ) {
			cin >> left >> right >> weight;
			A[left][right] = A[right][left] = min(A[left][right], weight);
		}

		for ( int u = 1; u <= nnode; u++ )
			for ( int v = u+1; v <= nnode; v++ ) {
				if ( A[u][v] == INFTY ) continue;
				G[u].push_back(E.size());
				G[v].push_back(E.size());
				E.push_back(Edge(u, v, A[u][v]));
			}

		vector<int> shortestPath;
		int shortestLength = INFTY;
		for ( int i = 0; i < E.size(); i++ ) {
			vector<int> path;

			E[i].hide();
			const int length = compute(E[i].left, E[i].right, path, shortestLength-E[i].weight);
			E[i].restore();

			if ( length != INFTY && length+E[i].weight < shortestLength )
				shortestLength = length+E[i].weight, shortestPath = path;
		}

		if ( shortestLength == INFTY ) {
			cout << "No solution." << endl;
			continue;
		}

		cout << shortestPath[0];
		for ( int i = 1; i < shortestPath.size(); i++ ) cout << ' ' << shortestPath[i];
		cout << endl;
	}

	return 0;
}