#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

vector <vector <pair <int, int>>> v;
vector <int> d;
vector <int> p;
vector <vector <int>> roads;

bool operator>(vector <int>& a, vector <int>& b) {
    int i = 0;
    while (i < (int)a.size()) {
        if (a[i] != b[i]) {
            return a[i] > b[i];
        }
        ++i;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    v.resize(n + 1, {});
    d.resize(n + 1, -1);
    p.resize(n + 1, -1);
    roads.resize(n + 1, {});
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a != b) {
            v[a].push_back({ b, c });
            v[b].push_back({ a, c });
        }
    }
    queue <pair <int, int>> q;
    q.push({1, 0});
    d[1] = 0;
    while (!q.empty()) {
        pair <int, int> s = q.front();
        int start = s.first;
        q.pop();
        if (start == n) {
            break;
        }
        for (auto x : v[start]) {
            if (x.first == s.second) continue;
            if (d[x.first] == -1) {
                d[x.first] = d[start] + 1;
                p[x.first] = start;
                roads[x.first] = roads[start];
                roads[x.first].push_back(x.second);
                q.push({ x.first, start });
            }
            else {
                if (d[x.first] == d[start] + 1) {
                    roads[start].push_back(x.second);
                    if (roads[x.first] > roads[start]) {
                        roads[x.first] = roads[start];
                    }
                    roads[start].pop_back();
                }
            }
        }
        roads[start].clear();
    }
    cout << roads[n].size() << "\n";
    for (int x : roads[n]) cout << x << " ";
    return 0;
}