/*
   Dear God, make it alright
   Only You can make it alright
   Dear Lord, make it alright
   Nothing else ever feels right
*/

//#pragma GCC optimize("Ofast,unroll-loops")
#include<algorithm>
#include<fstream>
#include<iostream>
#include<set>
#include<forward_list>
#include<vector>
#include<tuple>

using namespace std;

//#define int ll

typedef long long ll;
typedef long double ld;
#define sz(x) int((x).size())

template<class T>
T ScanInt(FILE* input) {
    int c = 0;
    T x = 0;
    for(; c < '0' || c > '9'; c = fgetc(input));
    for(; c >= '0' && c <= '9'; c = fgetc(input)) {
        x = (x << 1) + (x << 3) + c - '0';
    }
    return x;
}

void ToStartFile(FILE* fptr) {
    fseek(fptr, 0, SEEK_SET);
}

const int N = 2e5;

struct Tree {
    pair<int, int> t[4 * N];

    Tree() {
        fill(t, t + 4 * N, make_pair(2e9, 0));
    }

    void update(int v, int l, int r, int pos, int val) {
        if (l == r) {
            t[v] = { val, pos };
        } else {
            int m = (l + r) / 2;

            if (pos <= m) {
                update(2 * v, l, m, pos, val);
            } else {
                update(2 * v + 1, m + 1, r, pos, val);
            }

            t[v] = min(t[2 * v], t[2 * v + 1]);
        }
    }

    pair<int, int> get() {
        return t[1];
    }

    void set(int pos, int val) {
        update(1, 0, N - 1, pos, val);
    }
} tree;


int n, m;
int d[N], p[N];

forward_list<pair<int, int>> g[N];

signed main() {
    freopen("output.txt", "w", stdout);

    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    const int MAX_EDGES = 5e5;

    FILE* input = fopen("input.txt", "r");
    n = ScanInt<int>(input);
    m = ScanInt<int>(input);
    int from, to, weight;

    array<int, 1002> cnt;
    fill(cnt.begin(), cnt.end(), 0);

    for (int i = 0; i < m; ++i) {
        from = ScanInt<int>(input);
        to = ScanInt<int>(input);
        weight = ScanInt<int>(input);

        cout << from << " " << to << " " << weight << " " << endl;

        --from, --to;
        ++cnt[weight];
    }

    cout << endl;

    int lim = 0, pref = 0;
    while (lim <= 1000) {
        pref += cnt[lim];
        if (pref > MAX_EDGES) {
            --lim;
            break;
        } else {
            ++lim;
        }
    }

    ToStartFile(input);

    for (int i = 0; i < m; ++i) {
        from = ScanInt<int>(input);
        to = ScanInt<int>(input);
        weight = ScanInt<int>(input);

        cout << from << " " << to << " " << weight << " " << endl;

        --from, --to;
        if (weight <= lim) {
            g[from].push_front({ to, weight });
            g[to].push_front({ from, weight });
        }
    }

    fclose(input);

    fill(d, d + N, 2e9);
    d[0] = 0;
    tree.set(0, 0);

    while (true) {
        auto [dist, u] = tree.get();
        if (dist == 2e9) break;

        tree.set(u, 2e9);

        while (!g[u].empty()) {
            auto [v, w] = *g[u].begin();
            g[u].pop_front();

            cout << u << " " << v << " " << w << endl;

            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                p[v] = u;
                tree.set(v, d[v]);


                /*
                while (s.size() >= MAX_EDGES) {
                    s.erase(--s.end());
                }
                */

                //cout << u << " " << v << endl;
            }
        }
    }

    vector<int> ans;
    for (int u = n - 1; u; u = p[u]) {
        ans.push_back(u);
    }

    ans.push_back(0);
    reverse(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for (int x : ans) {
        cout << x + 1 << " ";
    }

    return 0;
}