#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

static int L[100][100];

struct edge_t {
	int a, b;
	int length;
};

struct route_t {
	list<int> points;
	int length;
};

bool operator <(const edge_t &e1, const edge_t &e2)
{
	if(e1.length != e2.length) {
		return e1.length < e2.length;
	}
	else {
		return (e1.a < e2.a) || (e1.a == e2.a && e1.b < e2.b);
	}
}

bool operator <(const route_t &r1, const route_t &r2)
{
	if(r1.length != r2.length) return r1.length > r2.length;
	return r1.points > r2.points;
}

int main(void)
{
	int n, m;
	while(cin >> n >> m) {
		if(n == -1) break;

		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				L[i][j] = -1;
			}
		}

		for(int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			--a; --b;
			if(L[a][b] == -1 || L[a][b] > c) {
				L[a][b] = L[b][a] = c;
			}
		}

		list<edge_t> edges;
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				edge_t e;
				if(L[i][j] > 0) {
					e.a = i;
					e.b = j;
					e.length = L[i][j];
					edges.push_back(e);
				}
			}
		}

		edges.sort();

		vector<int> g(n);
		for(int i = 0; i < n; i++) {
			g[i] = i;
		}

		list<edge_t>::iterator p, p_tmp;

		p = edges.begin();
		while(p != edges.end()) {
			if(g[p->a] == g[p->b]) break;
			int tmp = g[p->b];
			for(int i = 0; i < n; i++) {
				if(g[i] == tmp) g[i] = g[p->a];
			}
			++p;
		}

		if(p == edges.end()) {
			cout << "No solution." << endl;
			continue;
		}

		int s = p->a;
		int t = p->b;
		cout << s << " " << t << endl;
		p_tmp = p;

		p = edges.begin();
		while(p != p_tmp) {
			if(g[p->a] == g[s]) continue;
			L[p->a][p->b] = L[p->b][p->a] = -1;
			++p;
		}

		while(p != edges.end()) {
			L[p->a][p->b] = L[p->b][p->a] = -1;
			++p;
		}

		priority_queue<route_t> q;

		route_t init;
		init.points.push_back(s);
		init.length = 0;
		q.push(init);

		bool flag = false;

		while(!q.empty() && !flag) {
			route_t r = q.top();
			q.pop();

			int pos = r.points.back();

			for(int i = 0; i < n; i++) {
				if(L[pos][i] < 0) continue;

				route_t new_r = r;
				new_r.points.push_back(i);
				new_r.length += L[pos][i];

				if(i == t) {
					list<int>::iterator pp;

					pp = new_r.points.begin();
					while(pp != new_r.points.end()) {
						if(pp != new_r.points.begin()) cout << " ";
						cout << (*pp + 1);
						++pp;
					}

					cout << endl;

					flag = true;
					break;
				}

				q.push(new_r);
			}
		}

		if(!flag) {
			cout << "No solution." << endl;
		}
	}

	return 0;
}