#include <algorithm>
#include <iostream>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <vector>
#include <string>
#include <set>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstring>

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define llong long long
#define zero(a) fabs(a) < 1e-9
#define resz(a, n) a.clear(), a.resize(n)
#define same(a, n) memset(a, n, sizeof(a))
#define make(a, b) make_pair(a, b)

using namespace std;

const int MAXN = 105;
const int INF = 1000000000;

int n, m, dist[MAXN], adj[MAXN][MAXN], e[MAXN][MAXN];

vector< int > path(int s, int q) {
    vector< int > ret;
    while (adj[s][q] != 0) {
        ret.push_back(q);
        for (int i = 0; i < n; i++)
            if (adj[s][q] == adj[s][i] + e[q][i]) {
                q = i;
                break;
            }
    }
    return ret;
}

int main() {
    for (int t = 1; ; t++) {
        scanf("%d", &n);
        if (n < 0)
            break;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++)
                e[i][j] = e[j][i] = adj[i][j] = adj[j][i] = INF;
            e[i][i] = adj[i][i] = 0;
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            --u, --v;
            e[u][v] = e[v][u] = adj[u][v] = adj[v][u] = min(adj[u][v], w);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
        int ans = INF, x, y, z;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (adj[i][j] != adj[i][k] + e[j][k] && adj[i][k] != adj[i][j] + e[j][k]) {
                        if (adj[i][j] + adj[i][k] + e[j][k] < ans) {
                            ans = adj[i][j] + adj[i][k] + e[j][k];
                            x = j, y = k, z = i;
                        }
                    }
        if (ans == INF)
            printf("No solution.\n");
        else {
            vector< int > ret = path(z, x), q = path(z, y);
            ret.push_back(z);
            for (int j = sz(q) - 1; j >= 0; j--)
                ret.push_back(q[j]);
            printf("%d", ret[0] + 1);
            for (int i = 1; i < sz(ret); i++)
                printf(" %d", ret[i] + 1);
            printf("\n");
        }
    }
    return 0;
}