#include <iostream>
#include <vector>
using namespace std;

const int N = 100;
vector<pair<int, int>> g[N];
int dist[N][N];
int pre[N][N];

int main() {
    ios::sync_with_stdio(false);
    while (true) {
        int n, m;
        cin >> n;
        if (n == -1) {
            break;
        }
        for (int a = 0; a < n; ++a) {
            g[a].clear();
            dist[a][a] = 0;
            pre[a][a] = -1;
            for (int b = a + 1; b < n; ++b) {
                dist[a][b] = -1;
                dist[b][a] = -1;
            }
        }
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int a, b, d;
            cin >> a >> b >> d;
            --a, --b;
            g[a].emplace_back(b, d);
            g[b].emplace_back(a, d);
        }
        int mlen = -1;
        vector<int> path;
        for (int curr = 0; curr < n; ++curr) {
            for (int i = 0; i < g[curr].size(); ++i) {
                int a = g[curr][i].first, ad = g[curr][i].second;
                dist[curr][a] = ad;
                dist[a][curr] = ad;
                pre[curr][a] = curr;
                pre[a][curr] = a;
                if (a < curr) {
                    for (int j = 0; j < i; ++j) {
                        int b = g[curr][j].first, bd = g[curr][j].second;
                        if (a != b && dist[a][b] != -1 && (mlen == -1 || dist[a][b] + ad + bd < mlen)) {
                            mlen = dist[a][b] + ad + bd;
                            path.clear();
                            for (int node = b; node != -1; node = pre[a][node]) {
                                path.emplace_back(node);
                            }
                            path.emplace_back(curr);
                        }
                    }
                }
            }
            for (auto conn: g[curr]) {
                int a = conn.first;
                if (a < curr) {
                    for (int b = 0; b < curr; ++b) {
                        if (dist[a][b] != -1 && (dist[curr][b] == -1 || dist[curr][a] + dist[a][b] < dist[curr][b])) {
                            dist[curr][b] = dist[curr][a] + dist[a][b];
                            dist[b][curr] = dist[b][a] + dist[a][curr];
                            pre[curr][b] = pre[a][b];
                            pre[b][curr] = pre[a][curr];
                        }
                    }
                }
            }
            for (int a = 1; a < curr; ++a) {
                for (int b = 0; b < a; ++b) {
                    if (dist[a][curr] != -1 && dist[curr][b] != -1 && (dist[a][b] == -1 || dist[a][curr] + dist[curr][b] < dist[a][b])) {
                        dist[a][b] = dist[a][curr] + dist[curr][b];
                        dist[b][a] = dist[b][curr] + dist[curr][a];
                        pre[a][b] = pre[curr][b];
                        pre[b][a] = pre[curr][a];
                    }
                }
            }
        }
        if (mlen == -1) {
            cout << "No solution.";
        } else {
            for (int node: path) {
                cout << node + 1 << ' ';
            }
        }
        cout << '\n';
    }
}