/*
测试输入：
9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4

测试输出
*/
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1010, M = 100010;

int n, m;
int hs[N], ht[N], e[M], w[M], ne[M], idx;  // 顶点表示事件，边表示活动

int ve[N], vl[N];  // 事件允许的最早发生时间, 事件允许的最晚发生时间
// int ee[M], el[M];  // 活动的最早发生时间, 活动的最晚发生时间

int d[N];  // 每个点的入度
int q[N];  // 拓扑排序数组

vector<int> path;
vector<vector<int>> res;

void add(int h[], int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void topsort()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = hs[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
            {
                q[++ tt] = j;
            }
        }
    }
}

void critical_path()
{
    topsort();

    ve[1] = 0;
    for (int k = 0; k < n; ++ k)
    {
        int ver = q[k];
        for(int i = hs[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            ve[j] = max(ve[j], ve[ver] + w[i]);
        }
    }

    memset(vl, 0x3f, sizeof vl);
    vl[n] = ve[n];
    for (int k = n - 1; k >= 0; -- k)
    {
        int ver = q[k];
        for (int i = ht[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            vl[j] = min(vl[j], vl[ver] - w[i]);
        }
    }
}

void dfs(int u)
{
    path.push_back(u);

    if (hs[u] == -1)
    {
        res.push_back(path);
    }

    for (int i = hs[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (ve[j] - vl[j] == 0) dfs(j);
    }

    path.pop_back();
}
int main() {

    cin >> n >> m;
    memset(hs, -1, sizeof hs);
    memset(ht, -1, sizeof ht);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(hs, a, b, c);
        add(ht, b, a, c);
        d[b]++;
    }

    // 输入满足1号点是源点，n号点是汇点
    critical_path();

    dfs(1);

    for (auto &t : res) {
        for (int i = 0; i < t.size(); i++)
            cout << t[i] << ' ';
        cout << endl;
    }

    return 0;
}